Why is quick sort better than counting sort?

Question

Quick sort:

• worst case o(n^2)
• average case O(nlogn)

Counting sort:

• in all cases o(n)

Both quick sort and counting sort are stable algorithms.

If these two conditions are present, why is quick sort still better than counting sort?

Answer 1

Sorts aren't always necessarily 'better' than one another. In certain situations, quicksort might be preferred for a number of reasons:

1. Quicksort is in place, unlike counting sort, which has to create a number of arrays (e.g. use more memory) to do its work.

2. It may seem like counting sort is O(n), but take a look at the intermediate counting array that has to be created. The counting array length is essentially the difference between the largest and smallest elements in your original array. If the range is really big, this counting array is massive. For example, what if your array only has two elements, but the two elements are 1 and 9999999? And this counting array has to be processed (all that summation and counting stuff). So really, the run time of counting sort is O(n+k) where k is the difference between the largest and smallest elements in the original array.

3. Finally, counting sort seems...difficult to implement if the elements you're trying to sort are not numbers. How would it work for strings?