Another way to look at it: Sorting is linear in the size of the input in bytes, but not item count. It's only comparison sort that happens to be O(n log n).