Now, think back to 1986. That is when I submitted a big group of sort routines as my practical for my O-level. It was for the C64 and was used in a sprite-multiplexer. 1-Simple bubble sort. 2-Bubble with early exit. 3-Bubble with reducing sort size (after 1 itteration, 1 number is sorted). 4-Quicksort 5-binary sort Now, one that people may not know of, as invented by Sensible Software: 6-Bucket sort The last one is the interesting one. The thing is, a multiplex sort doesn't have to be perfect, just quite close. These guys divided the Y-position by 2 and then placed the number in the bottom 1/2 of the stack. If there was already a number there, they checked the next position until they found a free space. It was very fast and I never got it to fall over. Anyone else come across unusual or even unique sort routines?
my favourite has to be mergesort for linked lists http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html I've always meant to code a multiplexor with it. I used it after an insertion sort ground to it's knees. The other side to that is a binary search of the linked list. I've only used it with string keys, whether it has much of an advantage with chars/shorts/longs I don't know.
Sensible software wasn't founded till 1986... and bucket sort was invented in 1978 by Wlodzimierz Dobosiewicz (according to my algorithms class). I've always thought randomized quicksort was nice when a quick randomization is availible. What's fun though is to try and find some odd opcode that does some funky swizzling to allow you to do... whatever better.
