Count Sort Algorithm efficiency

algorithmssorting

As I read a book about "Algorithm Analysis", I came across count_sort Algorithm.
However, I have read elsewhere that "Quick Sort/ Merge Sort" are the best and the most efficient sorting algorithms. I found this confusing because the complexity of count_sort is O(n+k), which is better than Mergesort and Quicksort which are O(n ln n).

My question:

  • What is the problem with this sorting Algorithm?

  • What are the best sorting Algorithms?

    def count_sort(seq):
    b, c = [], defaultdict(list)
    for x in seq:
        c[x].append(x)

    for k in range(min(c), max(c)+1):
        b.extend(c[k])
    return b

Best Answer

Counting sorts fail when there are large key values (the k in the O(n)). This means that if you have a large variety of key values, counting sort will be slow. Radix sort can help solve that problem but it does nothing for other issue. Both counting and radix sort are only valid for integer keys. While not a terribly serious limitation, it does mean that Radix Sort's value for the number of digits in a key should not be considered constant.

There's also the small matter of space complexity and stability of sorting. Radix sort requires a stable sorting algorithm to be used as a subsort. Counting sort is stable, provided that you use a separate input and output structure. If you don't then you wind up with an unstable sort. That is, you may wind up with elements in the wrong order.

"Best" is a very loaded term. There is no "best" sorting algorithm. It will depend on a variety of factors including time complexity, space complexity, ability to parallelize the implementation and the ease of implementation.

Related Topic