Exploring Perfect Sorting Algorithms

[viv0411]

Is quick sort the most efficient algorithm or there is a possibility of a perfect sorting algorithm to be discovered?

 

[mgb_phys]

quick sort isn't even the most efficient current algorithm, it's worst case is O(n^2) but is quick and easy to code and the inner loop fits in the CPU cache so is fast enough normally.

merge and heap sorts are both O(n ln n) worst case but in practice are slower.

 

[rcgldr]

Merge sort can be faster than quicksort, especially when using pointers to data where the average compare size (before a mismatch) is greater than a pointer size. For true random data, I used a hybrid radix (bucket) / merge sort, which was the fastest, but required a large amount of memory.

Previous threads on sorting. I included some test results in post #16 of the thread in the first link:

https://www.physicsforums.com/showthread.php?t=218369

https://www.physicsforums.com/showthread.php?t=181589