« "unsubscribe" | Main | in praise of display calibration »

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

References (1)

References allow you to track sources for this article, as well as articles that were written in response to this article.
  • Response
    Response: jaket kulit
    openben - shinyblog - linear time sorting, or, why remedial courses are not just for dullards

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.

2.25.2008 at 01:37 PM | Unregistered CommenterAnonymous

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

3.12.2008 at 05:18 PM | Unregistered CommenterWesley

PostPost a New Comment

Enter your information below to add a new comment.

My response is on my own website »
Author Email (optional):
Author URL (optional):
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>