If you know more information about the items being sorted, you can sort them in linear time. Show that a collection of N 16-bit integers can be sorted in O(N) time. (Hint: Maintain an array indexed from 0 to 65,535.)