linear time sorting, or, why remedial courses are not just for dullards
Thursday, January 31, 2008 at 1:27PM I've been listening to an introductory course on algorithms from MIT OpenCourseware. Today I learned that it is possible to sort integers in linear time!! The technique I learned this morning, counting sort, only works for a particular kind of input: a list of n integers in the range 0..k. (Or any known range; map it to 0..k for convenience.) If k is much smaller than n, you can sort in Θ(n + k). That's linear time, people!
I'm 33, an Ivy League graduate, and I just discovered it's possible to sort in linear time! Where was I in (ahem) 1998 when Roberto Tamassia was teaching this? Well, it looks like this year's equivalent class at Brown (now cs0160, then cs21) doesn't counting sort in the lecture notes. Or maybe I slept through it; I was a sophomore.
My point: reviewing a subject you used to know, from a different perspective and with more experience than you had at 18, can blow your mind with mind-blowing information that you might have missed the first time through.
WE CAN SORT INTEGERS IN LINEAR TIME! (for sets of integers meeting the requirement above.)
Reader Comments (2)
In real life you're still limited by 2^32 or so numbers, which makes nlogn=32*2^32. So, first find a linear time sorting algorithm with c<32 (much less) and then you'll have a _reason_ to freak out.
n should be the number of numbers, not the number range, in Big-O notation. So I don't follow the anonymous comment.
But if your numbers are 0...k, which is much smaller than n, then a hash map of size k would let you sort in Theta(n).