
# Main 'do' loop is borrowed from Knuth ("Structured programming with
# go to Statements", Example 7) who swiped it from Dijkstra.

sub quicksort_ {
  # sort the elements of @a[$m..$n]
  my ($a, $m, $n) = @_;
  return if $n - $m <= 0;

  # if the array has only two elements, just put them in order
  if ($n - $m == 1) {
    @{$a}[$m,$n] = @{$a}[$n,$m] if $a->[$m] > $a->[$n];
    return;
  }

  # $v is the so-called 'pivot'
  my $v = $a->[$n];
  my $up = 1;
  my ($i, $j) = ($m, $n);

  # This arranges that the array is divided into two parts:
  # those elements that are < $v, and those that are >= $v
  # at the end, @a[$m..$j-1] are < $v, and 
  #             @a[$j..$n]   are >= $v
  do {
    if ($up) {
      if ($a->[$i] > $v) {
        $a->[$j] = $a->[$i]; $up = 0;
      }
    } else {
      if ($v > $a->[$j]) {
        $a->[$i] = $a->[$j]; $up = 1;
      }
    }
    if ($up) {
      ++$i;
    } else {
      --$j;
    }

  } while ($i < $j);
  $a->[$j] = $v;

# Now we sort the two halves of the array recursively.
  quicksort_($a, $m, $j-1);
  quicksort_($a, $j, $n);
}

sub quicksort {
  my @a = @_;
  quicksort_(\@a, 0, $#a);
  @a;
}
for (1..20) {
  push @a, int(rand(20));
}

@s = quicksort(@a);
print "@a\n@s\n";

