David Greaves / Guy Belloch

Tree quicksort: immutable data structures:

datatype 'a seq = | Empty
                  | Leaf of 'a
                  | Node of 'a seq * 'a seq


fun append Empty b = b
  | append a Empty = a
  | append a b = Node(a,b)


fun filter f Empty = Empty
  | filter f Leaf x = if f x then Leaf x else Empty
  | filter f Node(l,r) = append (filter f l) (filter f r)


fun qsort Empty = Empty
  | qsort S =
    let val pivot = first S
        val left  = filter (fn x => x < pivot) S
        val mid   = filter (fn x => x = pivot) S
        val right = filter (fn x => x > pivot) S
    in append (qsort left) (append mid (qsort right))

We can parallelise this by running the left, mid and right filters as separate tasks. Can make recursive call inside the task as well.

The immutable version may run faster or with less energy on a multicore CPU owing to less cache traffic?  Far fewer write evictions.