A few range questions

Charles Smith via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Tue Jan 5 15:54:36 PST 2016


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.


More information about the Digitalmars-d-learn mailing list