3 ms·
"The ideal sorting algorithm would have the following properties: - Stable: Equal keys aren't reordered. - Operates in place, requiring O(1) extra space. - W
by wgman 10y ago
"The ideal sorting algorithm would have the following properties:
- Stable: Equal keys aren't reordered.
- Operates in place, requiring O(1) extra space.
- Worst-case O(n·lg(n)) key comparisons.
- Worst-case O(n) swaps.
- Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.
There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application."
Is there any formal proof that such an algorithm doesn't exist? Are some of those criterion mutually exclusive?
- nightcracker 10y agoMost of these are possible to combine (see for example https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort), but I feel that this subset is impossible together: - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. I don't have a formal proof, but I believe one should be possible.
- phunehehe0 10y agoI went through the list of algorithms in Wikipedia [0] and a reader pointed out that block sort [1] is an interesting case. It has all the best properties listed, except the worst case swaps, which I can't find in Wikipedia. [0]: https://phunehehe.net/best-sorting-algorithm/ https://phunehehe.net/best-sorting-algorithm/ [1]: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
- alejohausner 10y agoWell, spaghetti sort runs in linear time: O(n) time is spent setting up the device, and O(n) reading out the result. The actual sorting step is O(1) !!! Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).