# What is the most obscure sorting algorithm you know? [closed]

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?

• Must come back to read. Nov 24, 2010 at 5:31
• Nice timing with this, my data structures class just started covering sorts. Now, not only do I get an understanding of basic sorts, but also the crazy ones too. Nov 24, 2010 at 15:05

Ever heard of Patience sorting? Well now you have...

• Interesting, Bazaar uses it to resolve merges. Nov 24, 2010 at 6:13

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)

• Bogosort can trivially be made more pessimal in the best-case by reversing the order of its steps: first, shuffle. If sorted, then stop. Dec 22, 2010 at 19:07
• @Alex: no. That doesn’t change anything. Bogosort would still be finished after the first step because as chance had it, the shuffling would have sorted the sequence. Bogosort still exhibits a pronounced best-case behaviour with fundamentally different run-time (O(n)) from its worst case and average case. Slowsort simply does not have this. Dec 22, 2010 at 20:12
• Ah, I was thinking only of initial conditions, not of execution paths! Dec 27, 2010 at 14:18
• Love this :) Nothing like brute force...
– user1249
Sep 7, 2011 at 12:32

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 :-).

• I like this one. I especially like the idea of "Quantum bogosort" :-) Nov 24, 2010 at 7:25

Another obscure "algorithm" is Intelligent Design Sort - but no algorithm is faster or has less memory consumption :)

• One of the best features of that algorithm is that we just know it works -- there's no need to analyze or prove anything. Sep 7, 2011 at 7:29

Sleep Sort is rather novel.

    #!/bin/bash
function f() {
sleep "$1" echo "$1"
}
while [ -n "$1" ] do f "$1" &
shift
done
wait


example 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.

• This is quite similar in idea to “sleep sort” and interestingly enough is used in bioinformatics for sequencing DNA (Sanger sequencing). Sep 7, 2011 at 10:07

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.

• Do you still have the source for this? I'd be interested to check it out!
– sova
Dec 22, 2010 at 21:12
• No source, it was for a non obsolete machine for a company that ultimately laid me off. The table lookup isn't hard:sb1=1&((a2-a1)>>63);sb2=2&((a3-a1)>>62);...index=sb1|sb2|sb3... followed by a table lookup of the order. Dec 23, 2010 at 2:38

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.

Dont remember the name, but it was basically

while Array not sorted

rearrange the array in a random order

• This is bogosort, mentioned in other answers. Sep 7, 2011 at 7:09

## Shell sort

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