I would probably use counting sort. This is not generally used outside of sorting a bunch of integer numbers that fall within a small range precisely because it uses a lot of memory. For e.g., to sort number in the range of 1 to 10,000, you will need an array C[1...10,000]. It can be extended to sort a set of any kind of stuff that has total ordering relationship between them, and is O(n) time. Only down side is that memory used will be insane depending on the range of values whatever you are sorting will take.