Quicksort

Divide, conquer, combine

Quicksort (invented by Sir Tony Hoare) follows the divide-and-conquer paradigm:

1. Choose a pivot element a from the input.
2. Divide: partition the remaining elements into those ≤ a and those > a.
3. Conquer: recursively sort each partition.
4. Combine: append the sorted left partition to the pivot followed by the sorted right partition.

List-based implementation

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

Three clauses:

• Empty list: already sorted.
• Singleton list [x]: already sorted (this special case avoids unnecessary work).
• Two or more elements: use the head a as pivot, partition the tail bs.

The locally declared part function accumulates elements ≤ pivot in l and elements > pivot in r.

Complexity analysis

Case	Recurrence	Complexity
Average case	T(n) = 2_T_(n/2) + n	O(n log n)
Worst case	T(n+1) = T(n) + n	O(_n_²)

Average case: with random data, the pivot typically divides the input into roughly equal halves. On the course benchmarks, quicksort sorts 10,000 random numbers in ~0.74 seconds.

Worst case: when the input is already sorted or reverse-sorted, nearly all elements fall into one partition. The work is not divided evenly, and complexity degenerates to quadratic. Randomising the input (or choosing a random pivot) makes the worst case highly unlikely in practice.