On Tuesday, 5 January 2016 at 22:34:52 UTC, Ali Çehreli wrote:
>> Algorithm's Sort: 76 ms, 910 μs, and 8 hnsecs
>> Counting Sort : 21 ms, 563 μs, and 9 hnsecs
> Awesome
I am amazed! :) countingSort() beats algorithmSort() almost
always. :)
Yeah, I've been reading an algorithm book, and this was in there.
It has O(elementCount + valueCount) time complexity under a
correct implementation, so it is fast. Also its best case is
quick sort's worst case (lots of duplicated data), at which point
it has O(elementCount) time complexity. I think D's sort uses
timsort, so I'd expect it to be no worse.
