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.

^{[5] }C. A. R. Hoare. 1961. Algorithm 63: Partition, Algorithm 64: Quicksort, and Algorithm 65: Find. *Commun. ACM* 4, 7 (July 1961), 321-322.