Quicksort

Quicksort is an algorithm developed by C. A. R. Hoare in 1960 to sort a sequence of elements into order. Quicksort works by dividing a sequence into two sub-sequences.

An element is selected from the sequence and called the pivot. The sequence is then re-arranged so all elements with a value less than the pivot are before the pivot and all elements with a greater value are after it.

The sub-sequences before and after the pivot are then recursively sorted.

Implementation in Redcode:

          org    qsort

          stack  equ outer-2
          pivot  equ outer-1

outer     mov    p,              <stack
          mov    {p,             pivot

inner     slt    pivot,          >p
y         djn    inner,          #LENGTH-1
          jmz    done,           y
          mov    <p,             *p
          mov    {p,             @p
          djn    inner,          y

done      mov.a  @stack,         p
          mov.ba p,              @stack
          mov    pivot,          >p

qsort     mov.ab p,              y
          sub.b  p,              y

          slt    y,              #2
          jmp    outer,          <y

          mov.f  >stack,         p
          jmn    qsort,          p

p         dat    FIRST+LENGTH,   FIRST