Necessary and Sufficient

Problem: You have 1 million objects in memory (it's a big machine). Each object represents a customer and therefore has a Name and AgeInYears property. You need to sort the customers by AgeInYears.

Solution: Many technical folks immediately rack their brain over the various sorting algorithms and if they are any good will offer up quickSort, or maybe mergeSort, and tell you it has O(n.log₂n) running time. But you need to stop and think about the problem for a minute and not be constrained by textbook knowledge. What's the age range of the customers? It couldn't be more than a hundred or so right (0-100)? So how about we create 100 lists - one for each age in this range - and then make a single pass through all 1 million customers adding them to the relevant list. That involves precisely n comparisons thus this has O(n) run time complexity. Of course we still need to merge the 100 lists to get the end result but that is trivial to do and doesn't add to the run time complexity. Now that's thinking outside the box!