# Count Sort Algorithm efficiency

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
• 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