What algorithm is faster than Quick Sort?

[engineer2004]

Gurus,

Are there any algorithms out there that are faster than quick sort?

If so what are they and where can I find more information about them?

Thanks

[yiannakop]

Hi engineer2004.
Quicksort is mostly used in programming because it has the best order. Though, there are some algorithms that have a better worst case complexity. Here is a table:

                    Order      WorstCase
Merge Sort        Nlog(N)   Nlog(N)
Quick Sort         Nlog(N)    N^2
Heap Sort         Nlog(N)    Nlog(N)
Selection Sort   N^2         N^2

Of course, the worst case complexity (N^2) is rarely achieved for the quick sort algorithm. Another thing is that Merge sort is easier to implement than the quicksort algorithm, but it uses more memory.
Generally, there are no other faster algorithms than Nlog(N) order. This is for numbers (and strings of course). There are some other algorithms which are ONLY for string sorting which are N-order (they are called Radix - Sort, or sth like that). Generally, search the net for all these algorithms and you'll find much...

[engineer2004]

Thanks! Appreciate the answer!

[Shanin]

Hello, I am curious.

Do the three sorting algorithms have same performance? the orders are appeared same, in contrast to your explanation.

Hi engineer2004.
Quicksort is mostly used in programming because it has the best order. Though, there are some algorithms that have a better worst case complexity. Here is a table:

                    Order      WorstCase
Merge Sort        Nlog(N)   Nlog(N)
Quick Sort         Nlog(N)    N^2
Heap Sort         Nlog(N)    Nlog(N)
Selection Sort   N^2         N^2

Of course, the worst case complexity (N^2) is rarely achieved for the quick sort algorithm. Another thing is that Merge sort is easier to implement than the quicksort algorithm, but it uses more memory.
Generally, there are no other faster algorithms than Nlog(N) order. This is for numbers (and strings of course). There are some other algorithms which are ONLY for string sorting which are N-order (they are called Radix - Sort, or sth like that). Generally, search the net for all these algorithms and you'll find much...

[KevinHall]

Radix sort can have better performance for both typical and worst case scenarios. But as with merge sort it requires more memory. It also requires that things be able to be classified in a certain way. Generally, radix sort only works well for integers and strings.

[yiannakop]

Hello, I am curious.

Do the three sorting algorithms have same performance? the orders are appeared same, in contrast to your explanation.

What I said is that the 3 first algorithms have the same order, but different worst-case complexities. I also mentioned some differences in implementation. I don't see where did I not follow the table...

[KevinHall]

Hello, I am curious.
Do the three sorting algorithms have same performance?

Just because two algorithms have the same complexity doesn't mean they are just as efficient or just as fast. It basically tells you how the algorithm performance worsens as the data set grows.

Assume one algorthm always takes exactly 10 times as long as another algorithm to execute. Well both algorithms would hve the same complexity. Complexity is therefore not a good measure of relative performance.

For more information on complexity and "big O notation" look here.

[KevinHall]

Oh and for the record, radix sort has a typical complexity of O(n).