1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – KWillets Mar 4 '18 at 17:45
  • $\begingroup$ @KWillets I though it did considering that the partitions get smaller, enough to fit a cache. $\endgroup$ – Olumide Mar 4 '18 at 17:47
  • $\begingroup$ They don't always get smaller. $\endgroup$ – KWillets Mar 4 '18 at 17:49
1
$\begingroup$

You've rediscovered radix sort.

$\endgroup$
  • $\begingroup$ I've been doing a bit more research, isn't it closer to postman's sort? rrsd.com/software_development/postmans_sort/cuj/cuj.htm $\endgroup$ – Olumide Mar 4 '18 at 2:23
  • $\begingroup$ @Olumide Postman's sort is a radix sort. It says as much on the Radix Sort Wikipedia page. On the Bucket Sort Wikipedia page which covers Postman's sort, it incorrectly suggests that radix sort is constrained to a number of buckets that is a power of two. In the metaphor used by radix sort, postman's sort is a most significant digit first radix sort where the key is represented as a number in a potentially mixed radix number system. $\endgroup$ – Derek Elkins Mar 4 '18 at 10:02
  • $\begingroup$ @DerekElkins I agree. But the postman's sort has a hierarchical component which I'm not certain radix sort prescribes. $\endgroup$ – Olumide Mar 4 '18 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.