# Sorting n-tuples

I've just hashed up the following hair-brained idea of how to sort n-tuples of integers, as demonstrated below with a set of 3-tuples:

[ 4 , 1 , 3 ]
[ 1 , 2 , 1 ]
[ 2 , 2 , 1 ]
[ 2 , 1 , 1 ]
[ 1 , 1 , 1 ]
[ 2 , 1 , 2 ]
[ 3 , 1 , 3 ]
[ 1 , 2 , 2 ]
[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]


First "partition" data by 1st dimension, thusly (as shown by the dotted lines)

[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 1 ]
......................
[ 2 , 1 , 2 ]
[ 2 , 2 , 1 ]
[ 2 , 1 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]
[ 3 , 1 , 3 ]
......................
[ 4 , 1 , 3 ]


Further next, I "partition" the previous partition by the 2nd dimension

[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 1 ]
.....................
[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
......................
[ 2 , 1 , 2 ]
[ 2 , 1 , 1 ]
......................
[ 2 , 2 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]
[ 3 , 1 , 3 ]
......................
[ 4 , 1 , 3 ]


Finally I partition by 3rd dimension

[ 1 , 1 , 1 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 3 ]
.....................
[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
......................
[ 2 , 1 , 1 ]
[ 2 , 1 , 2 ]
......................
[ 2 , 2 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 3 ]
[ 3 , 1 , 4 ]
......................
[ 4 , 1 , 3 ]


This seems to have the potential of being cache-friendly. Is it a sensible algorithm (or totally stupid) or have am I reinvented the wheel here?

• It's not particularly cache-friendly, as it does a separate pass for each radix. If the tuples/strings have long distinguishing prefixes, it thrashes. – KWillets Mar 4 '18 at 17:45
• @KWillets I though it did considering that the partitions get smaller, enough to fit a cache. – Olumide Mar 4 '18 at 17:47
• They don't always get smaller. – KWillets Mar 4 '18 at 17:49