## linear time sorting, or, why remedial courses are not just for dullards

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).