Almost all of the students are going to be somewhere between 17 and 23 years old, so you first do one pass as a bucket sort for each of those seven values. Then sort the remaining students however you want. While it's technically still O(n log n), almost everyone is sorted in that first pass, so it's practically indistinguishable from O(n).
That is actually a decent optimization. If you know the final cardinality, you just create that many buckets, and drop records in it. Not unlike how histograms work.
