Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share
4  
Must come back to read. –  Mark C Nov 24 '10 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. –  Jason Nov 24 '10 at 15:05
comments disabled on deleted / locked posts

locked by World Engineer Apr 3 '13 at 21:44

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. More info: help center.

closed as not constructive by ChrisF Sep 7 '11 at 8:53

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

14 Answers

up vote 9 down vote accepted

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

share
1  
Interesting, Bazaar uses it to resolve merges. –  Tim Post Nov 24 '10 at 6:13
add comment

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.

share
add comment

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

share
    
I like this one. I especially like the idea of "Quantum bogosort" :-) –  Dean Harding Nov 24 '10 at 7:25
    
+1 Made me laugh. –  Klaim Nov 24 '10 at 12:43
add comment

I think the bubble sort would be the wrong answer in this situation too

:)

share
1  
+1, I get it. :) –  greyfade Nov 24 '10 at 8:38
add comment

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 $\Omega(n^\frac{\log_2n}{2+\epsilon})$ 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)
share
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. –  Alex Feinman Dec 22 '10 at 19:07
3  
@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. –  Konrad Rudolph Dec 22 '10 at 20:12
    
Ah, I was thinking only of initial conditions, not of execution paths! –  Alex Feinman Dec 27 '10 at 14:18
    
Love this :) Nothing like brute force... –  user1249 Sep 7 '11 at 12:32
add comment

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

share
    
One of the best features of that algorithm is that we just know it works -- there's no need to analyze or prove anything. –  Caleb Sep 7 '11 at 7:29
add comment

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.

share
    
Do you still have the source for this? I'd be interested to check it out! –  sova Dec 22 '10 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. –  Omega Centauri Dec 23 '10 at 2:38
add comment

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

share
add comment

Dont remember the name, but it was basically

while Array not sorted

  rearrange the array in a random order
share
    
This is bogosort, mentioned in other answers. –  MatrixFrog Sep 7 '11 at 7:09
add comment

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

share
add comment

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
share
add comment

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

share
add comment

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.

share
    
This is quite similar in idea to “sleep sort” and interestingly enough is used in bioinformatics for sequencing DNA (Sanger sequencing). –  Konrad Rudolph Sep 7 '11 at 10:07
add comment

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.

share
add comment

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