Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Perfect sort

  1. Jun 10, 2010 #1
    Is quick sort the most efficient algorithm or there is a possibility of a perfect sorting algorithm to be discovered?
  2. jcsd
  3. Jun 10, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Jun 11, 2010 #3


    User Avatar
    Homework Helper

    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:


Share this great discussion with others via Reddit, Google+, Twitter, or Facebook