0

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
    
5
  • Why do you say that this is O(n+k)? How do you think defaultdict is implemented? Commented Sep 2, 2014 at 2:27
  • defaultdict is a python package check: stackoverflow.com/questions/5900578/… Commented Sep 2, 2014 at 21:13
  • 1
    Yes, I know what defaultdict is. However, using it is not free in terms of complexity. Commented Sep 2, 2014 at 21:15
  • True ! I wanted to illustrate how can we build sort algo in a very quick way. But still that we can remplace it with L= [{x:x} for x in list seq] Commented Sep 2, 2014 at 21:17
  • Most of the time you are sorting things that are not integers, and only have a < to order them by. Counting sort can only be "better" when it is applicable
    – Caleth
    Commented Apr 30, 2018 at 8:52

1 Answer 1

6

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.

2
  • Radix sort is not limited to integers. Read the first paragraph of that Wikipedia article you linked. Commented May 10, 2018 at 20:05
  • They are only valid for integer keys as stated, which can map to a variety of value types also as stated.
    – user28988
    Commented May 10, 2018 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.