Sorting is the gateway problem. Every comparison-based sort needs at least Ω(n log n) comparisons in the worst case. Merge sort and heapsort hit this bound. Quicksort hits it on average, with better constants.
Insertion sort
Walk through the array left to right. For each element, slide it into its correct position among the already-sorted prefix. O(n²) worst case, but O(n) when the input is nearly sorted. Good for small arrays.
Scheme
; Insertion sort: simple, O(n^2), good for small inputs
(define (insertion-sort lst)
(if (null? lst) (list)
(insert (car lst) (insertion-sort (cdr lst)))))
(define (insert x sorted)
(cond ((null? sorted) (list x))
((<= x (car sorted)) (cons x sorted))
(else (cons (car sorted) (insert x (cdr sorted))))))
(display "Unsorted: (5 3 8 1 7 2 6 4)") (newline)
(display "Sorted: ")
(display (insertion-sort (list 53817264)))
Split in half, sort each half, merge. Always O(n log n). Uses O(n) extra space. Stable. The workhorse of external sorting.
Scheme
; Merge sort: always O(n log n), stable
(define (merge-sort lst)
(if (or (null? lst) (null? (cdr lst)))
lst
(let* ((mid (quotient (length lst) 2))
(left (take lst mid))
(right (drop lst mid)))
(merge-lists (merge-sort left)
(merge-sort right)))))
(define (take lst n)
(if (= n 0) (list)
(cons (car lst) (take (cdr lst) (- n 1)))))
(define (drop lst n)
(if (= n 0) lst
(drop (cdr lst) (- n 1))))
(define (merge-lists a b)
(cond ((null? a) b)
((null? b) a)
((<= (car a) (car b))
(cons (car a) (merge-lists (cdr a) b)))
(else
(cons (car b) (merge-lists a (cdr b))))))
(display (merge-sort (list 382743398210)))
The n log n lower bound
Any comparison-based sort must make at least log_2(n!) comparisons in the worst case. By Stirling, log_2(n!) is Θ(n log n). You cannot do better with comparisons alone. Non-comparison sorts (counting sort, radix sort) beat this by using extra information about the keys.
Neighbors
Cross-references
🪄 SICP — comparison: functional vs imperative approaches to the same algorithms