Algorithms from zero
Simple sorts
You want to sort an array. The fast algorithms (merge sort, quicksort) are complex: divide the array, merge or partition, recurse. Before you learn those, understand the simple ones: selection sort, insertion sort, and bubble sort. They all run in O(n²) time—one nested loop inside another. They are slow on large data but fast to code and easy to understand. And insertion sort has a secret: when the array is nearly sorted, it runs in O(n) time. Learn these, and the fast ones will make sense.
After this lesson you understand three simple sorting algorithms (selection sort, insertion sort, and bubble sort), why they all run in O(n²) time (nested passes), how insertion sort adapts to O(n) on nearly sorted input, why all three are in-place and use O(1) space, and when it is safe to use them (small arrays or pre-sorted data) versus when to upgrade to O(n log n) algorithms.
The core insight: nested loops = O(n²)
All simple sorts use a nested structure: an outer loop over passes, and an inner loop to find/place one element. n passes × n comparisons per pass = O(n²).
Selection sort: repeatedly find the minimum
Selection sort divides the array into two parts: a sorted prefix (left) and an unsorted suffix (right). In each pass, scan the unsorted part, find the minimum, and swap it into the next sorted position.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}Why O(n²)? On pass i, you scan n - i elements to find the minimum. Total: n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n²), regardless of input order.
Insertion sort: grow a sorted prefix
Insertion sort builds the sorted array from left to right, one element at a time. For each new element, scan the sorted prefix from right to left, shift larger elements right, and insert the new element into its correct spot.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Why O(n²) worst case? When the array is reversed (worst case), each insertion requires shifting all previous elements. But here is the magic: insertion sort is adaptive. If the array is already sorted or nearly sorted, the while loop never runs (or runs once), so the algorithm runs in O(n) time.
Bubble sort: repeatedly swap adjacent pairs
Bubble sort repeatedly walks through the array and swaps adjacent elements if they are out of order. Larger elements “bubble up” to the end. After each pass, the rightmost unsorted element is in place.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}Also O(n²) worst case. Pass after pass, each comparing neighbors. Bubble sort is the slowest of the three in practice—more comparisons and swaps than insertion sort.
Why all three are O(n²) and in-place
All three use O(1) space—only a few variables (indices, a temporary for swap). All have worst-case O(n²) because of the nested loop structure. But insertion sort is special: adaptive.
Let us code and trace selection sort and insertion sort with full detail.
Selection sort:
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
// Find the minimum in arr[i..end]
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap arr[i] and arr[minIndex]
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}Insertion sort:
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i]; // Element to insert
let j = i - 1;
// Shift elements greater than key one position right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key into its correct position
arr[j + 1] = key;
}
}Let us run both on unsorted and sorted input:
Let us trace insertion sort on [5, 3, 2, 1, 4] step by step:
1
function insertionSort(arr) {
2
for (let i = 1; i < arr.length; i++) {
3
const key = arr[i];
4
let j = i - 1;
5
while (j >= 0 && arr[j] > key) {
6
arr[j + 1] = arr[j];
7
j--;
8
}
9
arr[j + 1] = key;
10
}
11
}
| Algorithm | Worst case | Best case | Adaptive? | Space |
|---|---|---|---|---|
| Selection sort | O(n²) | O(n²) | No | O(1) |
| Insertion sort | O(n²) | O(n) | Yes | O(1) |
| Bubble sort | O(n²) | O(n) | Yes (with optimization) | O(1) |
Selection sort details:
- Always O(n²) because you must scan the entire unsorted suffix to find the minimum, even if the array is already sorted.
- Number of swaps: O(n).
Insertion sort details:
- Worst case O(n²): array is reverse-sorted. Each insertion shifts all previous elements.
- Best case O(n): array is already sorted. The while loop condition fails immediately, and you only do n comparisons.
- Adaptive: the number of comparisons depends on the number of inversions (out-of-order pairs). Nearly sorted input = few inversions = O(n).
Bubble sort details:
- O(n²) worst case: repeated swaps of adjacent pairs.
- O(n) best case (with optimization): if no swaps occur in a pass, the array is sorted. Stop early.
- Less efficient than insertion sort in practice—more swaps and comparisons.
In selection sort, why is the time complexity O(n²) even when the array is already sorted?
Insertion sort runs in O(n) time on a nearly sorted array. Why?
How many passes does selection sort make to sort an array of 5 elements?
Which algorithm is best for a large, already-sorted array?
What does 'in-place' mean for sorting algorithms?
lesson.inset.advantage
When to use simple sorts. Selection sort, insertion sort, and bubble sort are O(n²). Why use them? Small arrays (n ≤ ~50) or nearly sorted input. Insertion sort especially: it is simple, in-place, and highly adaptive. Many real systems use insertion sort for small data inside optimized O(n log n) algorithms (hybrid sorting).
Common mistake
Thinking selection sort can exit early. Selection sort always scans the entire unsorted suffix, even if it is already sorted. It cannot “notice” that the array is sorted and stop early. Bubble sort can (with an optimization: track if any swap occurred), but selection sort cannot. This is why insertion sort is better for pre-sorted data.
You need to sort a list of 10 elements. All three simple sorts (selection, insertion, bubble) are O(n²). Which should you choose?
Selection sort: Repeatedly find the minimum in the unsorted part and swap it into place. O(n²) always. No adaptivity.
Insertion sort: Grow a sorted prefix by inserting each new element into its correct spot. O(n²) worst case, but O(n) on sorted or nearly sorted input. Adaptive.
Bubble sort: Repeatedly swap adjacent out-of-order pairs. O(n²) worst case, O(n) best case (with optimization). Slower than insertion sort in practice.
All three are in-place and use O(1) auxiliary space. This matters on very large datasets or memory-constrained systems.
Key insight: All simple sorts are O(n²) due to the nested loop structure. Insertion sort is special: it adapts to input order, running O(n) on nearly sorted data. For large unsorted data, upgrade to O(n log n) algorithms (merge sort, quicksort) covered in the next lessons.
Why learn them? Understanding simple sorts teaches you the nested-loop structure. It prepares you for divide-and-conquer sorting (merge sort) and partitioning-based sorting (quicksort).