Merge Sort
You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.
Let n_{i} be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let n_{k} be the number of keys in each item.
The total time to sort the sequence is thus O(n_{k}(n_{i} + N)).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
