Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
I just read about cyclesort via a sortvis.org blog post. This is probably the most obscure one I have heard of so far, since it uses maths that I am not familiar with (detecting cycles in permutations of integer sets).
What is the most obscure one you know?
Slowsort works by multiply and surrender (as opposed to divide and conquer). It is interesting because it is provably the least efficient sorting algorithm that can be built (asymptotically, and with the restriction that such an algorithm, while being slow, must still all the time be working towards a result).
This offsets it from bogosort because in the best case, bogosort is quite efficient – namely, when the array is already sorted. Slowsort doesn’t “suffer” from such a best-case behaviour. Even in its best case, it still has runtime 
for ϵ > 0.
Here is its pseudocode, adapted from the German Wikipedia article:
function slowsort(A, i, j):
if i >= j: return
m = (i + j) / 2
slowsort(A, i, m)
slowsort(A, m + 1, j)
if A[j] < A[m]:
swap(A[j], A[m])
slowsort(A, i, j - 1)
I don't know if this counts as obscure, but one of the most ridiculous sorting "algorithms" is Bogosort. The links off the Bogosort page are fun too.
And there's this gem from the section on "quantum bogo-sort".
Arguably, creating 2N universes is also very memory-intensive.
Hmmm ... you could say that :-).
Another obscure "algorithm" is Intelligent Design Sort - but no algorithm is faster or has less memory consumption :)
Sleep Sort is rather novel.
#!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done waitexample usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7
I think the bubble sort would be the wrong answer in this situation too
:)
Knuth Volume 31, in the answer to one of the exercises, gives an implementation of a nameless sorting algorithm that's basically an ancient code golf -- the shortest sort you can write in MIX assembly language. The short code does comes at the oh-so-minor price of O(N3) complexity though...
1At least in the older editions. Given the modifications to MIXAL for the new edition, I'm not sure whether it's still there, or even makes the minuscule bit of sense in did in the original MIXAL.
For my data structures class I had to (explicitly) prove the correctness of Stooge sort. It has a running time of O(n^{log 3 / log 1.5}) = O(n^2.7095...).
I don't know if it's the most obscure, but spaghetti sort is one of the best in situations where you can use it.
One of the original Knuth books, "Sorting and Searching", had a middle fold-out that diagrammed a process which sorted a tape file using no hard disk. I think it used six tape drives, and explicitly showed when each was being read forward, read backwards, rewinding, or idle. Today it is a monument to an obsolete technology.
I once did an in vector registers bubble sort in CRAY assembler. The machine had a double shift instruction, which allowed you to shift the contents of a vector register up/down by one word. Put the every other point in two vector registers, then you could do a full bubble sort without ever having to make another memory reference until you are done. Except for the N**2 nature of bubble sort it was efficient.
I also once needed to do a floating point sort of a length 4 vector as fast as possible for a single sort. Did it by table lookup (the sign bit of A2-A1 is one bit, sign of A3-A1 forms another bit ..., then you look up the permutation vector in a table. It was actually the fastest solution I could come up with. Doesn't work well on modern architectures though, the floating and integer units are too separated.
Google Code Jam had a problem about an algorithm called Gorosort, which I think they invented for the problem.
Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of N different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations.
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3
Dont remember the name, but it was basically
while Array not sorted
rearrange the array in a random order
Maybe the algorithm itself isn't that obscure, but who can name an implementation that's actually used in practice? I can!
TIGCC (a GCC-based compiler for TI-89/92/V200 graphing calculators) uses Shell sort for the qsort implementation in its standard library:
__ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func)
{
unsigned short gap,byte_gap,i,j;
char *p,*a,*b,temp;
for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1) // Yes, this is not a quicksort,
{ // but works fast enough...
byte_gap=gap*(unsigned short)size;
for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
{
a=p; b=p+byte_gap;
if(cmp_func(a,b)<=0) break;
for(j=size;j;j--)
temp=*a, *a++=*b, *b++=temp;
}
}
}
Shell sort was chosen in favor of quicksort to keep code size low. Although it's asymptotic complexity is worse, the TI-89 doesn't have a whole lot of RAM (190K, minus the program size and the total size of any unarchived variables), so it is somewhat safe to assume that the number of items will be low.
A faster implementation was written after I complained about it being too slow in a program I was writing. It uses better gap sizes, along with assembly optimizations. It can be found here: qsort.c
