stooge sort

Stooge sort is discussed in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms. Wikipedia's article on Stooge sort describes the algorithm as follows:

• If the value at the end is smaller than the value at the start, swap them.
• If there are 3 or more elements in the current list subset,
  • Stooge sort the initial 2/3 of the list
  • Stooge sort the final 2/3 of the list
  • Stooge sort the initial 2/3 of the list again

Stooge sort is extremely inefficient. For example, sorting 100 elements requires in the region of 2.4 million cycles compared to around 3500 for quicksort and 8000 for insertion sort.

Implementation in Redcode:

          org    inner

          stack  equ outer-2
          temp   equ outer-1

outer     mov    p,              <stack
          sub.ba temp,           @stack
          mov    p,              <stack
          add.b  temp,           @stack
          sub.ba temp,           p
inner     slt    {p,             @p
          jmp    noexch,         }p

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST
          mov    temp,           }p

noexch    mov.ab p,              temp
          sub.b  p,              temp
          div    #3,             temp
          jmn    outer,          temp

finished  mov.f  >stack,         p
          jmn    inner,          p