Re:A beginner's guide to Big O notation (2009)
by hnkain on Thursday May 05, 2016 @11:02PM
(#11641402)
It doesn't invalidate what you say, but you're assuming there's a bounded number of different values in the array -- 2^k where k is your word size.
Under this assumption, a correctly implemented quicksort also runs in O(N) time.
Radix sort is a linear time sort because the hardware (random access memory) is built to allow constant-time lookup of memory. Radix sort wouldn't be linear time on a sequential access memory system, like tape, but merge sort would still be O(NlgN) on such a system.