Quadratic-time comparison sorts that are easy to reason about: bubble, insertion, selection and Shell sort.
Simple sorts are the quadratic comparison sorts: easy to write, easy to prove correct, and genuinely useful for small or nearly-sorted inputs. Production sorting routines such as Timsort and introsort still fall back to insertion sort for short runs, so understanding these algorithms is practical, not only historical.
Bubble sort repeatedly steps through the list, swapping adjacent out-of-order pairs until a pass makes no swaps. It is the canonical "first sort you learn&
Insertion sort builds a sorted prefix one element at a time, shifting each new element back to its correct position. It is fast on small or nearly-sorted…
Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into place. It is O(n²) on every input — never adaptive — but it makes the…
Shell sort generalizes insertion sort by sorting elements that are positions apart, then shrinking the gap until it reaches 1. By the time gap = 1, the array…
All four algorithms grow a sorted region one element at a time; they differ in how they choose the next element and how much data they move. Bubble sort swaps adjacent out-of-order pairs, so the largest remaining value drifts to the end each pass. Selection sort scans for the minimum and performs a single swap per pass. Insertion sort takes the next unsorted element and shifts it left into the sorted prefix. Shell sort runs insertion sort over elements that are a gap apart, shrinking the gap until it reaches one, which moves far-away elements quickly and beats the plain quadratic sorts in practice.
| Algorithm | Best | Average | Worst | Space | Stable | Adaptive |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes (early exit) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | No |
| Shell Sort | O(n log n) | gap-sequence dependent | O(n²) for Shell's gaps | O(1) | No | Partly |
For general-purpose sorting of large inputs use the language's built-in sort, which is an O(n log n) hybrid. The Mergesort and Timsort pages explain how those hybrids use insertion sort internally.