Sorting is usually the first real algorithm most of us write, and it's a great way to build intuition for time complexity, in-place mutation, and divide-and-conquer thinking. This guide works through the classic sorts in three groups:
- The simple O(n²) sorts — bubble, selection and insertion — plus merge sort, the first to reach O(n log n).
- The in-place O(n log n) sorts — quick sort and heap sort, which match merge sort's speed without its extra array.
- The non-comparison sorts — counting sort and radix sort, which beat the n log n limit by never comparing elements at all.
Each visualization is interactive: hit Play to watch it sort step by step, or Shuffle to try a different starting order.
Part 1: The simple sorts and merge sort
Bubble Sort
Bubble sort repeatedly walks through the array, comparing adjacent elements and swapping them if they're in the wrong order. The largest unsorted element "bubbles up" to its correct position at the end of each pass.
- Time complexity: O(n²) average and worst case, O(n) best case (already sorted, with an early-exit check)
- Space complexity: O(1) — sorts in place
- Stable: yes
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
Selection Sort
Selection sort splits the array into a sorted prefix and an unsorted suffix. On each pass, it scans the unsorted portion to find the minimum element and swaps it into place at the front of that portion.
- Time complexity: O(n²) in all cases — it always scans the remaining unsorted elements, even if the array is already sorted
- Space complexity: O(1) — sorts in place
- Stable: no (the swap can move an equal element past another)
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
Insertion Sort
Insertion sort builds up a sorted prefix one element at a time — it takes the next unsorted element and shifts it backward into its correct position within the already-sorted portion. It's the algorithm most people use intuitively when sorting a hand of playing cards.
- Time complexity: O(n²) average and worst case, O(n) best case (nearly sorted input)
- Space complexity: O(1) — sorts in place
- Stable: yes
- Efficient for small or nearly-sorted datasets, which is why it's often used as the base case inside hybrid sorts like Timsort
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
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;
}
return arr;
}
Merge Sort
Merge sort is divide-and-conquer: split the array in half recursively until each piece has one element, then merge pairs of sorted pieces back together. Unlike the previous three, it doesn't sort in place — merging requires auxiliary storage.
- Time complexity: O(n log n) in all cases — the split/merge structure doesn't depend on the input's initial order
- Space complexity: O(n) — needs extra space for the merge step
- Stable: yes
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0, k = left;
while (i < leftArr.length && j < rightArr.length) {
arr[k++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length) arr[k++] = leftArr[i++];
while (j < rightArr.length) arr[k++] = rightArr[j++];
}
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
Part 2: Quick sort and heap sort
Merge sort was the only one of the first four to hit O(n log n), but it paid for that speed with O(n) auxiliary space. Quick sort and heap sort get to O(n log n) without the extra array.
Quick Sort
Quick sort is divide-and-conquer like merge sort, but it does the work before recursing instead of after. Pick an element as the pivot, then partition the array so everything smaller than the pivot ends up on its left and everything larger on its right. After partitioning, the pivot is in its final sorted position — then recurse into the two halves on either side of it.
The implementation below uses the Lomuto partition scheme with the last
element as the pivot: walk a pointer j across the range, and every time
arr[j] is smaller than the pivot, swap it into the "smaller" region at the
front tracked by i.
- Time complexity: O(n log n) average, O(n²) worst case (already-sorted input with a last-element pivot degrades to one-sided partitions)
- Space complexity: O(log n) for the recursion stack — partitioning itself is in place
- Stable: no (partition swaps can reorder equal elements)
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low >= high) return arr;
const p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[high]] = [arr[high], arr[i]];
return i;
}
Why the pivot choice matters
The O(n²) worst case isn't a theoretical curiosity — it shows up whenever the pivot keeps landing at an extreme. With a last-element pivot, feeding quick sort an already-sorted array makes every partition split into "everything" and "nothing", so the recursion depth becomes n instead of log n. Common fixes:
- Random pivot — swap a random element into the pivot slot before partitioning; the worst case still exists but no fixed input triggers it reliably
- Median-of-three — use the median of the first, middle, and last elements, which handles sorted and reverse-sorted inputs well
- Introsort — start with quick sort, and switch to heap sort if the recursion gets suspiciously deep; this is what C++'s
std::sortdoes to guarantee O(n log n)
Despite the worst case, quick sort is usually the fastest comparison sort in practice: partitioning scans memory sequentially (cache-friendly) and the constant factors are small.
Heap Sort
Heap sort turns the array itself into a max-heap — a complete binary
tree, stored right inside the array, where every parent is greater than or
equal to its children. For the element at index i, its children live at
2i + 1 and 2i + 2. That layout means no pointers and no extra memory.
The algorithm runs in two phases:
- Heapify: walk backwards from the last parent node, sifting each element down until the whole array satisfies the heap property. The maximum is now at index 0.
- Extract: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and sift the new root down to restore the heap property. Repeat until the heap is empty — the array fills with sorted values from the back.
- Time complexity: O(n log n) in all cases — building the heap is O(n), and each of the n extractions costs O(log n)
- Space complexity: O(1) — fully in place, no recursion needed
- Stable: no (the root-to-back swaps jump over equal elements)
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
for (int end = n - 1; end > 0; end--) {
int temp = arr[0];
arr[0] = arr[end];
arr[end] = temp;
siftDown(arr, 0, end);
}
}
private static void siftDown(int[] arr, int i, int size) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest == i) return;
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest;
}
}
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
siftDown(arr, i, n);
}
for (let end = n - 1; end > 0; end--) {
[arr[0], arr[end]] = [arr[end], arr[0]];
siftDown(arr, 0, end);
}
return arr;
}
function siftDown(arr, i, size) {
while (true) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest === i) return;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
}
Heap sort's guaranteed O(n log n) and O(1) space look unbeatable on paper,
but its memory access pattern is the catch: sifting down jumps between
index i and 2i + 1, which scatters reads across the array and misses
the CPU cache far more than quick sort's sequential scans. That's why it's
usually the fallback (as in introsort) rather than the default.
Part 3: Sorting without comparisons
Every sort so far works by comparing pairs of elements. There's a proof that any comparison-based sort needs about n log n comparisons in the worst case — no clever algorithm can beat it.
But that proof only covers sorts that compare. If you know something about the values — say, they're integers between 0 and 100 — you can sort without comparing them at all.
Counting sort
The idea: count how many times each value appears, then write them out in order.
Sort 8 numbers that are all between 0 and 5. Comparison sorts can't beat O(n log n). But when the values come from a small known range, you don't need to compare them at all — you can count them.
function countingSort(nums, maxValue) {
const counts = new Array(maxValue + 1).fill(0);
for (const n of nums) counts[n]++; // 1. count
const out = [];
for (let v = 0; v <= maxValue; v++) { // 2. write out in order
for (let c = 0; c < counts[v]; c++) out.push(v);
}
return out;
}
countingSort([3, 1, 4, 1, 5, 2, 3, 0], 5); // [0, 1, 1, 2, 3, 3, 4, 5]
Time is O(n + k), where n is the number of items and k is the size of the value range. When k is small compared with n — ages, scores out of 100, bytes — that's linear time.
Sorting records, not just numbers
Usually you're sorting objects by a key: orders by status, people by age. Writing out bare values doesn't work then. Instead, turn the counts into running totals, which tell you where each key's block starts in the output, and place each record into its block:
function countingSortBy(items, key, maxKey) {
const counts = new Array(maxKey + 1).fill(0);
for (const item of items) counts[key(item)]++;
// starts[k] = index where the block for key k begins
const starts = new Array(maxKey + 1).fill(0);
for (let k = 1; k <= maxKey; k++) starts[k] = starts[k - 1] + counts[k - 1];
const out = new Array(items.length);
for (const item of items) out[starts[key(item)]++] = item;
return out;
}
Records are placed in input order within each block, so items with equal keys keep their original relative order. That property is called stability, and the next algorithm depends on it.
Radix sort: one digit at a time
Counting sort needs a small range. To sort large numbers — say, 32-bit integers or 10-digit phone numbers — radix sort applies counting sort once per digit, starting from the least significant one:
input: 170 45 75 90 802 24 2 66
by ones: 170 90 802 2 24 45 75 66
by tens: 802 2 24 45 66 170 75 90
by hundreds: 2 24 45 66 75 90 170 802
Each pass sorts by one digit, and because each pass is stable, the order from earlier (less significant) digits is preserved among numbers that tie on the current digit. After the last digit, everything is sorted.
function radixSort(nums) {
const max = Math.max(...nums);
let out = nums;
for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
out = countingSortBy(out, (n) => Math.floor(n / place) % 10, 9);
}
return out;
}
radixSort([170, 45, 75, 90, 802, 24, 2, 66]); // [2, 24, 45, 66, 75, 90, 170, 802]
With d digits, that's O(d × (n + 10)). For fixed-width keys — 32-bit integers sorted a byte at a time are just four passes — it's linear in n.
Comparison
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix sort | O(d × (n + b)) | O(d × (n + b)) | O(d × (n + b)) | O(n + b) | Yes |
k is the size of the value range, d the number of digits, and b the base (10 for decimal digits, 256 for bytes).
Which one to use
Bubble, selection, and insertion sort are all O(n²) and mainly useful for learning or tiny inputs — insertion sort is the pick of the three for nearly-sorted data, which is why hybrid sorts use it for small ranges.
Each of the three fast sorts gives something up: merge sort spends memory to stay stable, quick sort risks a rare O(n²) to be fastest on average, and heap sort accepts slower constants for guaranteed bounds with zero extra space. Real standard libraries hedge accordingly — Java sorts primitives with a tuned quick sort variant, sorts objects with Timsort (merge-based, because stability is part of the contract), and C++'s introsort blends all three: quick sort's speed, heap sort's guarantee, and insertion sort for tiny ranges.
Counting and radix sort earn their place when you're sorting millions of
small integers, building a histogram anyway, or need a stable sort by a
small key. In everyday JavaScript, array.sort((a, b) => a - b) is fast and
simple, and you should reach for it first — see
array sorting and comparators
for how to write comparators that don't surprise you.
Pitfalls with the non-comparison sorts
- A huge range kills counting sort. Sorting a few numbers between 0 and 10⁹ allocates a billion-entry array. Check k before choosing it.
- Negative numbers need an offset: subtract the minimum first.
- Radix sort must use a stable inner sort, and must go from the least significant digit up, or the passes undo each other.