Sunday, January 10, 2021

[gkxhydsu] best sorting algorithm

the hypothetical best sorting algorithm has O(n log n) worst-case time complexity (eliminates quicksort), requires O(1) additional space (eliminates mergesort), is stable (eliminates heapsort and quicksort), and is simple.

Wikipedia's list of sorting algorithms currently only has Block Sort satisfying the first 3 requirements, but it appears very complicated.

it's surprising that a simple algorithm, perhaps paying for simplicity with large constant factors hidden inside big-O, hasn't been discovered yet.  or a proof that no such algorithm exists, though that requires defining "simple".

No comments :