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