Tuesday, May 26, 2015

This sort starts with the list of items:
[13, 8, 10, 18, 0, 4, 2, 11, 12, 14, 7, 19, 1, 3, 17, 6, 15, 5, 9, 16]
Starting it takes the last three items, 16, 9 and 5, sorts them, and makes a 3 item "spearhead" like below and two empty piles L and M:

It then looks at the next item from the right, 15, and compares it to the items on the spearhead and finds where it will fall, either greater than 16, or less than 5, or between 9 and 16, or between 9 and 5... Since it is between 9 and 16 it pops 16 off the spearhead and puts 16 in the M pile and replaces it with 15...
It iterates the above step all the way across the list, the next number is 6 which falls between 5 and 9, so 6 replaces 5 and 5 goes in the L pile...
The next is 17 which is greater than 15 so goes directly into the M pile:
Then 3 which is less than 6 so goes in the L pile, then 1 goes in the L pile, 19 goes in the M pile, Then 7 is between 9 and 6 so replaces 6 and 6 goes in the L pile... The only other addendum is that you try to keep the piles the same size which might change the lead number, but in this case didn't...  In that case you would just replace the appropriate trailing number with the item that would make the pile too big, and move what was there to the lead and the lead to the other trailing spot and the number that was there into the other pile, keeping the two piles balanced...

And so on until you get:

Now we can recursively use the same notion on the two smaller lists until all are in order...
** Notes**
The right to left order I used might be replaced with 3 random numbers to start and using the next random nuumber from the unsorted to prevent bad performance when the list is already sorted, for example...