Sorting Algorithms - Complete Guide
Master essential sorting algorithms: Bubble, Selection, Insertion, Merge, Quick, and understanding stability and time complexity.
Introduction
What You'll Learn
- How key sorting algorithms work and when to use them
- Time/space complexity and stability of each algorithm
- In-place vs non in-place sorting
- Divide-and-conquer approach (Merge, Quick)
- Implementations in JavaScript/TypeScript
- Choosing the right sorting algorithm for constraints
Why This Topic is Important
Sorting is foundational for searching, data processing, and many higher-level algorithms. Understanding trade-offs helps you choose the right algorithm for performance-critical systems and interviews.
Real-World Applications
- Database ordering and indexing
- Displaying sorted lists in UIs
- Preprocessing for binary search
- Ranking/leaderboards
- Scheduling and prioritization
- Deduplication and merging datasets
Learning Objectives
- Implement classic sorting algorithms
- Compare complexities and stability
- Identify best/worst-case behaviors
- Select appropriate algorithm per scenario
- Reason about in-place vs extra-space trade-offs
Sorting Basics
Sorting rearranges elements into a specific order (ascending/descending). Efficiency depends on algorithm choice, input distribution, and constraints like memory and stability.
- **Stability**: Keeps equal elements in original order (important when items have secondary keys).
- **In-place**: Uses O(1) extra space vs allocating new arrays.
- **Best/Average/Worst**: Behavior can vary widely by input.
📊 Comparison:
Table comparing algorithms: Bubble O(n^2) stable/in-place; Selection O(n^2) unstable/in-place; Insertion O(n^2) avg, O(n) best (nearly sorted), stable/in-place; Merge O(n log n) stable/not in-place; Quick O(n log n) avg, O(n^2) worst, unstable/in-place (partition).
Alt text: Sorting algorithms complexity and stability table
Bubble Sort
function bubbleSort(arr) {
const a = [...arr];
for (let i = 0; i < a.length; i++) {
let swapped = false;
for (let j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
swapped = true;
}
}
if (!swapped) break; // early exit if already sorted
}
return a;
}Repeatedly swaps adjacent out-of-order elements. Stable, in-place. Best O(n) if nearly sorted, worst O(n^2).
Selection Sort
function selectionSort(arr) {
const a = [...arr];
for (let i = 0; i < a.length; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
if (min !== i) [a[i], a[min]] = [a[min], a[i]];
}
return a;
}Finds minimum each pass and swaps to front. Always O(n^2), in-place, not stable (swap can reorder equals).
Insertion Sort
function insertionSort(arr) {
const a = [...arr];
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return a;
}Builds sorted prefix by inserting each element. Stable, in-place. Great for small or nearly-sorted data (best O(n), worst O(n^2)).
Merge Sort
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 res = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) res.push(left[i++]);
else res.push(right[j++]);
}
return res.concat(left.slice(i)).concat(right.slice(j));
}Divide-and-conquer: split, sort halves, merge. Stable, not in-place (O(n) extra). Time O(n log n) always.
Quick Sort
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [], equal = [], right = [];
for (const x of arr) {
if (x < pivot) left.push(x);
else if (x > pivot) right.push(x);
else equal.push(x);
}
return [...quickSort(left), ...equal, ...quickSort(right)];
}Divide-and-conquer: partition by pivot. Average O(n log n), worst O(n^2) if pivot poor. In-place versions exist; this is simpler non in-place.
⚠️ Warning
Quick Sort worst-case is O(n^2) (e.g., already sorted with bad pivot). Mitigate with random or median-of-three pivot selection.
Choosing the Right Sort
- Small or nearly-sorted input → Insertion Sort
- Guaranteed O(n log n) and stable → Merge Sort
- Average-case fast, in-place → Quick Sort (with good pivot)
- Educational/simple but slow → Bubble/Selection
📊 Table:
Sorting decision table: Columns (Use When, Stable, Extra Space). Rows: Insertion (small/nearly-sorted, yes, O(1)); Merge (need stability, yes, O(n)); Quick (average speed/in-place, no, O(log n) stack); Bubble/Selection (only for teaching, bubble stable, selection not).
Alt text: Sorting algorithm decision guide
Practical Examples
Example 1: Insertion Sort on nearly-sorted array
console.log(insertionSort([1,2,4,3,5])); // [1,2,3,4,5]Nearly-sorted arrays run in close to O(n) with insertion sort.
Example 2: Merge Sort for stable sorting of objects
const people = [
{ name: "A", age: 30 },
{ name: "B", age: 25 },
{ name: "C", age: 30 }
];
// Stable sort by age keeps relative order of age=30
const sorted = mergeSort(people.map(p => p.age));Merge sort is stable; equal keys keep order. (Shown with ages; apply to paired data to maintain order.)
Example 3: Quick Sort average-case
console.log(quickSort([9,4,6,2,7,5]));Quick sort partitions around a pivot; average O(n log n).
Example 4: Bubble Sort early exit
console.log(bubbleSort([1,2,3,4])); // early exit after one passEarly-exit optimization makes bubble sort O(n) on sorted input.
Example 5: Selection Sort deterministic passes
console.log(selectionSort([3,1,2]));Selection sort always makes n-1 passes; good for education, not performance.
Quiz: Test Your Knowledge
1. Which sorting algorithm is stable and guarantees O(n log n) time?
2. Which algorithm is best for nearly-sorted small arrays?
3. Quick Sort worst-case occurs when:
4. Which is NOT in-place by default?
5. Which algorithm is always unstable (in basic form)?
Practice Exercises
Exercise 1: Implement Heap Sort
Write a heap sort implementation (build max-heap, then extract).
Show Hints
- Build heap in O(n) using bottom-up heapify
- Then swap first/last, heapify reduced heap
- Repeat until size 1
Exercise 2: Stable Sort by Secondary Key
Given an array of objects with fields (dept, name), sort by dept, preserving original order for same dept.
Show Hints
- Use stable algorithm (merge sort) or decorate-sort-undecorate
- Key: dept; keep indices to maintain order
Exercise 3: Quick Sort In-Place (Lomuto)
Implement in-place quick sort using Lomuto partition scheme.
Show Hints
- Partition with pivot at end
- i tracks boundary of smaller elements
- Recurse on subarrays
Exercise 4: Count Inversions with Merge Sort
Modify merge sort to count inversions in O(n log n).
Show Hints
- During merge, when right[j] < left[i], inversions += left.length - i
- Accumulate from subcalls
Exercise 5: Benchmark Sorts
Write a script to benchmark bubble, insertion, merge, and quick sort on random and nearly-sorted arrays.
Show Hints
- Use performance.now() (browser) or process.hrtime.bigint() (Node)
- Generate arrays of different sizes and orders