Sorting Overview
Sorting is one of the most studied problems in computer science. Nearly every application touches sorting: databases index sorted data, search engines rank results, file systems organize entries, and countless algorithms require sorted input as a precondition.
Understanding sorting algorithms teaches you fundamental techniques — divide and conquer, heaps, comparison lower bounds — that appear everywhere in DSA. And knowing which sort to pick in a given situation is a real engineering skill.
Why Sorting Matters
Binary search requires sorted data — O(n log n) sort once, O(log n) per query
Deduplication is trivial on sorted data — adjacent duplicates are easy to spot
Many greedy algorithms require sorted input (interval scheduling, activity selection)
Closest pair, median finding, order statistics — all easier on sorted data
Database JOINs and GROUP BY use sorting internally
Key Properties to Understand
Stable vs Unstable
A sort is stable if equal elements retain their original relative order after sorting. This matters when sorting objects by one key when they are already sorted by another key (e.g., sort by last name within each department).
// Stable sort preserves relative order of equal elements
const employees = [
{ name: 'Alice', dept: 'Engineering', salary: 100 },
{ name: 'Bob', dept: 'Marketing', salary: 80 },
{ name: 'Carol', dept: 'Engineering', salary: 120 },
{ name: 'Dave', dept: 'Marketing', salary: 90 },
];
// Sort by salary (already done above, in order 100, 80, 120, 90)
// Now sort by department stably:
// Engineering: Alice (100), Carol (120) — original salary order preserved within dept
// Marketing: Bob (80), Dave (90) — original salary order preserved within dept
// JavaScript's Array.sort() is guaranteed stable as of ES2019 (in modern engines)
employees.sort((a, b) => a.dept.localeCompare(b.dept));
// Result:
// { name: 'Alice', dept: 'Engineering', salary: 100 }
// { name: 'Carol', dept: 'Engineering', salary: 120 } ← Alice before Carol (original order)
// { name: 'Bob', dept: 'Marketing', salary: 80 }
// { name: 'Dave', dept: 'Marketing', salary: 90 } ← Bob before Dave (original order)In-place vs Out-of-place
An in-place sort rearranges elements within the original array using O(1) or O(log n) extra memory. An out-of-place sort creates a new array to store results (O(n) extra space).
Comparison vs Non-comparison
Comparison sorts determine order by comparing pairs of elements. The theoretical lower bound for comparison sorts is Ω(n log n) — no comparison sort can be faster in the worst case.
Non-comparison sorts (counting sort, radix sort, bucket sort) use the actual values of elements rather than comparing them. They can achieve O(n) but require assumptions about the input (bounded integers, uniform distribution, etc.).
Comprehensive Algorithm Comparison Table
Algorithm | Best | Average | Worst | Space | Stable? | Type |
|---|---|---|---|---|---|---|
Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Comparison |
Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No* | Comparison |
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Comparison |
Shell Sort | O(n log n) | O(n^1.5) | O(n²) | O(1) | No | Comparison |
Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Comparison |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Comparison |
Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Comparison |
Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Hybrid |
Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Non-comparison |
Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Non-comparison |
Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n+k) | Yes* | Non-comparison |
*Selection sort can be made stable with careful implementation. Bucket sort stability depends on the sort used within each bucket. Tim Sort is the hybrid used by Python's sort() and Java's Arrays.sort().
The O(n log n) Lower Bound
Any comparison-based sorting algorithm requires at least Ω(n log n) comparisons in the worst case. The proof uses decision trees:
- A comparison sort produces a decision tree where each internal node is a comparison
- The tree must have at least n! leaves (one per permutation of the input)
- A binary tree with n! leaves has height ≥ log₂(n!) ≈ n log n (by Stirling's approximation)
- Therefore, at least n log n comparisons are needed in the worst case
This means merge sort, heap sort, and Tim sort are asymptotically optimal among comparison sorts. Quicksort is optimal on average. You cannot do better with comparisons alone.
Simple O(n²) Sorts and When to Use Them
// Insertion sort — O(n²) worst/average, O(n) best (already sorted)
// Best for: small arrays (n < 20), nearly sorted data, online streaming
// Used as the base case in Tim Sort and intro sort
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]; // shift right
j--;
}
arr[j + 1] = key;
}
return arr;
}
// Bubble sort — O(n²) all cases (with early exit: O(n) if sorted)
// Best for: educational purposes and... that's about it
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
let swapped = false;
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]];
swapped = true;
}
}
if (!swapped) break; // early exit if no swaps — array is sorted
}
return arr;
}
// Selection sort — O(n²) always, O(n) swaps (minimizes writes — good for flash memory!)
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return arr;
}When to Choose Each Algorithm
Situation | Best Choice | Why |
|---|---|---|
General purpose, unknown data | Tim Sort / built-in sort | Adaptive, stable, O(n log n) |
Need guaranteed O(n log n) worst case | Merge Sort or Heap Sort | No O(n²) pathological case |
Memory constrained, in-place required | Quick Sort or Heap Sort | O(log n) and O(1) extra space |
Nearly sorted data | Insertion Sort or Tim Sort | O(n) or close to it |
Stability required | Merge Sort or Tim Sort | Preserves relative order of equals |
Small integers in known range | Counting Sort | O(n+k), beats comparison bound |
Fixed-width integers (32-bit, etc.) | Radix Sort | O(nk) often faster than O(n log n) |
Floating point in [0, 1] | Bucket Sort | O(n) expected for uniform distribution |
Tiny arrays (n < 20) | Insertion Sort | Low overhead beats O(n log n) sorts |
External sorting (disk) | Merge Sort | Sequential access pattern suits disk I/O |
JavaScript Array.sort()
// JavaScript's built-in sort is guaranteed stable since ES2019
// V8 uses Tim Sort (adaptive merge sort + insertion sort)
// Default: converts to string, sorts lexicographically (BAD for numbers!)
[10, 9, 2, 1, 100].sort(); // → [1, 10, 100, 2, 9] WRONG for numbers!
// Correct: provide a comparator
[10, 9, 2, 1, 100].sort((a, b) => a - b); // ascending → [1, 2, 9, 10, 100]
[10, 9, 2, 1, 100].sort((a, b) => b - a); // descending → [100, 10, 9, 2, 1]
// Sort objects
const people = [{ name: 'Charlie', age: 25 }, { name: 'Alice', age: 30 }, { name: 'Bob', age: 25 }];
people.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));
// Sort by age ascending; break ties by name alphabetically
// Sort strings
['banana', 'Apple', 'cherry'].sort(); // case-sensitive
['banana', 'Apple', 'cherry'].sort((a, b) => a.localeCompare(b)); // locale-aware