## 5.4. Quicksort

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.