The original quicksort algorithm ^[5] was designed for efficient execution on a uniprocessor. Encoding it as a functional program typically ignores its efficient rearrangement of the elements of an array. Further, no known implementation highlights its concurrent aspects. The following program attempts to overcome these two limitations. The program is mostly functional in its structure, though it manipulates the array elements in place. We encode parts of the algorithm as concurrent activities where sequentiality is unneeded.

The following listing gives the implementation of the quicksort function which sorts the array a in place. The auxiliary function sort sorts the subarray given by indices s through t by calling part to partition the subarray and then recursively sorting the partitions.

{- Perform Quicksort on a list -}

def quicksort(a) =

  def swap(x, y) = a(x)? >z> a(x) := a(y)? >> a(y) := z

  {- Partition the elements based on pivot point 'p' -}
  def part(p, s, t) =
    def lr(i) = if i <: t && a(i)? <= p then lr(i+1) else i
    def rl(i) = if a(i)? :> p then rl(i-1) else i

    #
      (lr(s), rl(t)) >(s', t')>
      ( Ift (s' + 1 <: t') >> swap(s', t') >> part(p, s'+1, t'-1)
      | Ift (s' + 1 = t') >> swap(s', t') >> s'
      | Ift (s' + 1 :> t') >> t'
      )

  {- Sort the elements -}
  def sort(s, t) =
     if s >= t then signal
     else part(a(s)?, s+1, t) >m>
          swap(m, s) >>
          (sort(s, m-1), sort(m+1, t)) >>
          signal

  sort(0, a.length?-1)

val a = Array(3)
a(0) := 1 >>
a(1) := 3 >>
a(2) := 2 >>

quicksort(a) >> arrayToList(a)

{-
OUTPUT:
[1, 2, 3]
-}

The function part partitions the subarray given by indices s through t into two partitions, one containing values less than or equal to p and the other containing values > p. The last index of the lower partition is returned. The value at a(s-1) is assumed to be less than or equal to p --- this is satisfied by choosing p = a(s-1)? initially. To create the partitions, part calls two auxiliary functions lr and rl concurrently. These functions scan from the left and right of the subarray respectively, looking for out-of-place elements. Once two such elements have been found, they are swapped using the auxiliary function swap, and then the unscanned portion of the subarray is partitioned further. Partitioning is complete when the entire subarray has been scanned.

This program uses the syntactic sugar x? for x.read() and x := y for x.write(y). Also note that the expression a(i) returns a reference to the element of array a at index i, counting from 0.