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
    
  • Why do you say that this is O(n+k)? How do you think defaultdict is implemented? – Greg Hewgill Sep 2 '14 at 2:27
  • defaultdict is a python package check: stackoverflow.com/questions/5900578/… – user3001937 Sep 2 '14 at 21:13
  • 1
    Yes, I know what defaultdict is. However, using it is not free in terms of complexity. – Greg Hewgill Sep 2 '14 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] – user3001937 Sep 2 '14 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 Apr 30 '18 at 8:52
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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