A better test would be to implement all of the popular sorting algorithms in c and run benchmarks on them. That way it is a level playing field. I suspect counting sort will win for random data, especially if the range of values is restricted such as from 0 to 65535 (16 bit unsigned numbers). However in real life, we tend to sort strings a lot more than numbers, so a good sorting algorithm must work well on strings such as full names.
If you are sorting integers within a reasonable range of values, why not just use counting sort? Also, you didn't test heapsort in this comparison. Something I have an interest in is to find out which sort algorithm performs very well in an almost sorted starting state and then write a routine to quickly put it in that state. For example, suppose we had 100,000 random integers to sort. The 1st step would be to put them in an almost sorted state (such as partitioning them like Quicksort does), then use some algorithm that works very well on almost sorted data.
how can timsort be so fast? I tried it (not in python) and it is usually between merge and quick In random data. why's python's implementation different?
+Daniel De Lizaur yeah, I'm just as amazed and curious as you are. I read up on it a bit, but couldn't find enough details on it to code my own implementation of it.
Tim sort is probably implemented as a c extension rather than in regular python code (the latter being notoriously slow for this type of thing). If you were to either implement timsort yourself in regular python, or write one of the other algorithms as a c extension, the performance difference will most likely disappear.
