Append-Free Quicksort

Eliminating append

The standard quicksort uses @ to combine sorted partitions in the combine phase. This can be eliminated using an accumulating parameter sorted, following the same technique used to remove @ from list reversal.

let rec quik = function
  | ([], sorted) -> sorted
  | ([x], sorted) -> x::sorted
  | a::bs, sorted ->
     let rec part = function
       | l, r, [] -> quik (l, a :: quik (r, sorted))
       | l, r, x::xs ->
           if x <= a then
             part (x::l, r, xs)
           else
             part (l, x::r, xs)
     in
     part ([], [], bs)

How it works

Calling quik(xs, sorted) reverses the elements of xs and prepends them to sorted. The evaluation order inside part is significant:

1. quik (r, sorted) is performed first (sort the right partition and prepend to sorted).
2. The pivot a is consed onto that result.
3. quik (l, ...) sorts the left partition and prepends it.

The sorted parameter accumulates the result, replacing the repeated concatenation (quick l) @ (a :: quick r).

Speed comparison

The append-free version is significantly faster. An imperative Pascal quicksort (using in-place array swaps, from Sedgewick) is only slightly faster than quik. This near-agreement is surprising given that linked lists have more overhead than arrays. In realistic applications, comparisons dominate the runtime, and list overhead matters less than one might expect.

On the DECstation benchmarks, append-free quicksort sorts 10,000 random numbers in approximately 0.53 seconds, compared to 0.74 seconds for the append-based version.