Insertion Sort

How it works

Insertion sort builds the sorted output one element at a time by inserting each input element into its correct position among the already-sorted elements.

ins inserts a single element into a sorted list:

let rec ins x = function
  | [] -> [x]
  | y::ys -> if x <= y then x :: y :: ys
             else y :: ins x ys

On average, ins performs n/2 comparisons to insert into a list of length n.

insort applies ins to each element of the input:

let rec insort = function
  | [] -> []
  | x::xs -> ins x (insort xs)

Complexity

Measure	Value
Average comparisons	O(_n_²)
Worst-case comparisons	O(_n_²)
Tail-recursive?	No, but that is not the bottleneck

The quadratic runtime makes insertion sort nearly useless for large inputs. On the DECstation benchmarks referenced in the course, insertion sort took 174 seconds to sort 10,000 random numbers, while quicksort took 0.74 seconds: over 200 times slower.

Why study it?

Insertion sort is easy to code and illustrates fundamental concepts:

• It is the natural first attempt at a sorting algorithm.
• Mergesort and heapsort can be understood as refinements of insertion sort.
• For very small lists (length < 5 or so), insertion sort’s low constant factors can make it the fastest choice, and production quicksort implementations often switch to insertion sort for small partitions.

The bottleneck is the number of comparisons (O(_n_²)), not the absence of tail recursion. Making insertion sort iterative would not change its asymptotic complexity.