Why is quicksort used in practice?

performance algorithm sorting quicksort
halovi picture halovi · Apr 21, 2009 · Viewed 8.5k times · Source

Quicksort has a worst-case performance of O(n2), but is still used widely in practice anyway. Why is this?

Answer

vartec picture vartec · Apr 21, 2009

You shouldn't center only on worst case and only on time complexity. It's more about average than worst, and it's about time and space.

Quicksort:

  • has average time complexity of Θ(n log n);
  • can be implemented with space complexity of Θ(log n);

Also have in account that big O notation doesn't take in account any constants, but in practice it does make difference if the algorithm is few times faster. Θ(n log n) means, that algorithm executes in K n log(n), where K is constant. Quicksort is the comparison-sort algorithm with the lowest K.

Related questions

When should we use Radix sort?

It seems Radix sort has a very good average case performance, i.e. O(kN): http://en.wikipedia.org/wiki/Radix_sort Yet it seems like most people are still using Quick Sort - why is this?

Read More
Fast algorithm implementation to sort very small list

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the …

Read More
Fastest gap sequence for shell sort?

According to Marcin Ciura's Optimal (best known) sequence of increments for shell sort algorithm, the best sequence for shellsort is 1, 4, 10, 23, 57, 132, 301, 701..., but how can I generate such a sequence? In Marcin Ciura's paper, he said: Both Knuth’s and Hibbard’s …

Read More