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