Algorithms
Sorting Algorithms Ordering
Sorting is the process of rearranging elements in a defined order โ the bedrock of countless algorithms that rely on sorted input (binary search, two-pointer, merge intervals). Knowing which sort to apply and why is one of the most-tested skills in technical interviews.
01
Section One ยท Foundation
What is Sorting?
A sorting algorithm rearranges the elements of a collection into a total order โ typically ascending or descending. Sorting is foundational: binary search, merge-interval problems, frequency counting, and k-th element queries all assume sorted input. Algorithms fall into two broad families: comparison sorts (Merge, Quick, Heap โ bounded by ฮฉ(n log n)) and non-comparison sorts (Counting, Radix, Bucket โ can achieve O(n) under constraints). Choosing the right sort depends on input size, pre-sortedness, memory budget, and stability requirements.
Analogy: Think of sorting a hand of playing cards. Insertion sort copies how most people pick up and place cards one-by-one. Merge sort is like splitting the deck in half repeatedly until each pile is a single card, then merging pairs in order. Quick sort is like picking a "pivot" card, putting everything smaller to the left and larger to the right, then recursing on each pile.
Key Characteristics
Stable vs Unstable
โถ
Stable sorts preserve relative order of equal elements (Merge, Insertion, Counting). Quick and Heap are unstable.
In-Place vs Out-of-Place
โถ
In-place sorts use O(1) extra space (Quick, Heap). Merge sort needs O(n) auxiliary space.
Comparison Lower Bound
โถ
Any comparison-based sort requires at least ฮฉ(n log n) comparisons in the worst case โ proved via decision tree argument.
Adaptive
โถ
Adaptive sorts exploit existing order (Timsort, Insertion on nearly-sorted input) to run faster than their worst-case bound.
Algorithm Landscape
| Algorithm | Family | Stable | In-Place | Best | Average | Worst |
|---|---|---|---|---|---|---|
| Merge Sort | Comparison | โ | โ | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | Comparison | โ | โ | O(n log n) | O(n log n) | O(nยฒ) |
| Heap Sort | Comparison | โ | โ | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | Comparison | โ | โ | O(n) | O(nยฒ) | O(nยฒ) |
| Radix Sort | Non-Comparison | โ | โ | O(nk) | O(nk) | O(nk) |
| Counting Sort | Non-Comparison | โ | โ | O(n+k) | O(n+k) | O(n+k) |
02
Section Two ยท Core Algorithms
Algorithm Walkthroughs
Merge Sort โ Divide & Conquer
Recursively split the array in half, sort each half, then merge the two sorted halves. Guaranteed O(n log n) on all inputs.
| Step | Action | State After |
|---|---|---|
| 1 | Split array at mid-point into left and right halves | [5,3,8,1] โ [5,3] and [8,1] |
| 2 | Recursively sort each half until subarrays of size 1 | [3,5] and [1,8] |
| 3 | Merge: compare front elements of both halves, pick smaller, advance pointer | [1,3,5,8] |
Tip: Merge sort is the go-to for sorting linked lists (no random access needed) and for external sorting (files too big for RAM). Its stable sort property also makes it useful when secondary ordering matters.
Quick Sort โ Partition & Recurse
Choose a pivot, partition elements around it so all elements left < pivot < all elements right, then recurse on each partition.
| Step | Action | State After |
|---|---|---|
| 1 | Choose pivot (e.g. last element). Set left pointer at start. | pivot=4, arr=[3,6,8,10,1,2,4] |
| 2 | Walk j from lo to hi-1: if arr[j] โค pivot, swap arr[++i] with arr[j] | [3,2,1,4,10,6,8] (pivot at index 3) |
| 3 | Recurse on [0..pivot-1] and [pivot+1..n-1] | Each partition converges to sorted order |
Tip: Use random pivot selection or median-of-three to avoid O(nยฒ) on already-sorted input. Java's
Arrays.sort uses a dual-pivot quicksort for primitives.Heap Sort โ Build Heap + Extract
Build a max-heap in O(n), then repeatedly extract the maximum to sort in-place in O(n log n) guaranteed, with O(1) extra space.
| Step | Action | State After |
|---|---|---|
| 1 | Heapify (build max-heap): call sift-down from last internal node to root | Array satisfies heap property |
| 2 | Swap root (max) with last element; reduce heap size by 1 | Largest element placed at end |
| 3 | Sift-down root to restore heap; repeat steps 2โ3 until one element remains | Array fully sorted ascending |
Tip: Heap sort excels when you need worst-case O(n log n) with O(1) space and don't care about stability. It's less cache-friendly than merge/quick sort because heap traversal accesses non-contiguous memory.
Radix Sort โ Non-Comparison Linear Sort
Sort integers digit-by-digit from least significant digit (LSD) to most significant, using a stable sub-sort (counting sort) at each digit position.
| Step | Action | State After |
|---|---|---|
| 1 | Find max value to determine number of digit passes d | d = number of passes needed |
| 2 | For each digit position (1s, 10s, 100sโฆ): stable counting-sort on that digit | Array partially ordered through current digit |
| 3 | After all d passes, array is fully sorted | O(dยทn) total, O(n+k) space |
Tip: Radix sort beats comparison sorts when keys are integers with bounded digit count d โช log n (e.g., 32-bit ints โ d=10 decimal digits). Not suitable for floating-point or arbitrary objects.
Common Mistake: Using quick sort on already-sorted input with a fixed pivot (first or last element) causes O(nยฒ) performance. Always use random pivot or median-of-three. Also, forgetting that merge sort needs O(n) auxiliary space can cause OOM in memory-constrained environments.
03
Section Three ยท Visuals
Diagrams & Walkthroughs
Merge Sort โ Divide & Merge Tree
Quick Sort โ Partition Walkthrough
Complexity Curves Comparison
04
Section Four ยท Code
Implementations
Quick-reference Java merge sort โ click the button for full multi-language implementations.
// Merge Sort โ Java void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r); // stable O(n) merge
}
Sorting Algorithms โ Full Implementation
Java โ Merge Sort, Quick Sort, Heap Sort, Radix Sort
import java.util.Arrays;
public class SortingAlgorithms {
// โโ Merge Sort โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] left = Arrays.copyOfRange(arr, l, mid + 1);
int[] right = Arrays.copyOfRange(arr, mid + 1, r + 1);
int i = 0, j = 0, k = l;
while (i < left.length && j < right.length)
arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
// โโ Quick Sort โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
public static void quickSort(int[] arr, int lo, int hi) {
if (lo < hi) {
int p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
}
private static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (arr[j] <= pivot) { i++; int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
int t = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = t;
return i + 1;
}
// โโ Heap Sort โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n-1; i > 0; i--) {
int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int max = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[max]) max = l;
if (r < n && arr[r] > arr[max]) max = r;
if (max != i) {
int t = arr[i]; arr[i] = arr[max]; arr[max] = t;
heapify(arr, n, max);
}
}
// โโ Radix Sort (LSD, non-negative ints) โโโโโ
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) countByDigit(arr, exp);
}
private static void countByDigit(int[] arr, int exp) {
int n = arr.length;
int[] out = new int[n], count = new int[10];
for (int v : arr) count[(v/exp)%10]++;
for (int i = 1; i < 10; i++) count[i] += count[i-1];
for (int i = n-1; i >= 0; i--) out[--count[(arr[i]/exp)%10]] = arr[i];
System.arraycopy(out, 0, arr, 0, n);
}
}
Python โ Merge Sort, Quick Sort, Heap Sort, Radix Sort
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
i = j = 0; result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]: result.append(left[i]); i += 1
else: result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return result
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = _partition(arr, lo, hi)
quick_sort(arr, lo, p - 1); quick_sort(arr, p + 1, hi)
def _partition(arr, lo, hi):
pivot, i = arr[hi], lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
def heap_sort(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1): _heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]; _heapify(arr, i, 0)
def _heapify(arr, n, i):
mx = i; l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[mx]: mx = l
if r < n and arr[r] > arr[mx]: mx = r
if mx != i: arr[i], arr[mx] = arr[mx], arr[i]; _heapify(arr, n, mx)
def radix_sort(arr):
if not arr: return
exp = 1
while max(arr) // exp > 0: _count_by_digit(arr, exp); exp *= 10
def _count_by_digit(arr, exp):
n, count, out = len(arr), [0]*10, [0]*len(arr)
for v in arr: count[(v//exp)%10] += 1
for i in range(1, 10): count[i] += count[i-1]
for i in range(n-1, -1, -1):
d = (arr[i]//exp)%10; count[d] -= 1; out[count[d]] = arr[i]
arr[:] = out
JavaScript โ Merge Sort, Quick Sort, Heap Sort
// Merge Sort
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = arr.length >> 1;
return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}
function merge(l, r) {
const res = []; let i = 0, j = 0;
while (i < l.length && j < r.length)
res.push(l[i] <= r[j] ? l[i++] : r[j++]);
return res.concat(l.slice(i), r.slice(j));
}
// Quick Sort
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo < hi) {
const p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1); quickSort(arr, p + 1, hi);
}
}
function partition(arr, lo, hi) {
const pivot = arr[hi]; let i = lo - 1;
for (let j = lo; j < hi; j++)
if (arr[j] <= pivot) [arr[++i], arr[j]] = [arr[j], arr[i]];
[arr[i+1], arr[hi]] = [arr[hi], arr[i+1]];
return i + 1;
}
// Heap Sort
function heapSort(arr) {
const n = arr.length;
for (let i = Math.floor(n/2)-1; i >= 0; i--) heapify(arr, n, i);
for (let i = n-1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; heapify(arr, i, 0);
}
}
function heapify(arr, n, i) {
let m = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l] > arr[m]) m = l;
if (r < n && arr[r] > arr[m]) m = r;
if (m !== i) { [arr[i], arr[m]] = [arr[m], arr[i]]; heapify(arr, n, m); }
}
C# โ Merge Sort, Quick Sort, Heap Sort
using System;
public class SortingAlgorithms {
public static void MergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
MergeSort(arr, l, mid); MergeSort(arr, mid+1, r); Merge(arr, l, mid, r);
}
static void Merge(int[] arr, int l, int mid, int r) {
var left = arr[l..(mid+1)].ToArray();
var right = arr[(mid+1)..(r+1)].ToArray();
int i = 0, j = 0, k = l;
while (i < left.Length && j < right.Length)
arr[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < left.Length) arr[k++] = left[i++];
while (j < right.Length) arr[k++] = right[j++];
}
public static void QuickSort(int[] arr, int lo, int hi) {
if (lo < hi) { int p = Partition(arr,lo,hi); QuickSort(arr,lo,p-1); QuickSort(arr,p+1,hi); }
}
static int Partition(int[] arr, int lo, int hi) {
int pivot = arr[hi], i = lo-1;
for (int j = lo; j < hi; j++)
if (arr[j] <= pivot) { i++; (arr[i],arr[j])=(arr[j],arr[i]); }
(arr[i+1],arr[hi]) = (arr[hi],arr[i+1]); return i+1;
}
public static void HeapSort(int[] arr) {
int n = arr.Length;
for (int i = n/2-1; i >= 0; i--) Heapify(arr, n, i);
for (int i = n-1; i > 0; i--) { (arr[0],arr[i])=(arr[i],arr[0]); Heapify(arr,i,0); }
}
static void Heapify(int[] arr, int n, int i) {
int m = i, l = 2*i+1, r = 2*i+2;
if (l < n && arr[l]>arr[m]) m=l; if (r < n && arr[r]>arr[m]) m=r;
if (m!=i) { (arr[i],arr[m])=(arr[m],arr[i]); Heapify(arr,n,m); }
}
}
05
Section Five ยท Complexity
Time & Space Complexity
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | โ |
| Quick Sort | O(n log n) | O(n log n) | O(nยฒ)* | O(log n) | โ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | โ |
| Insertion Sort | O(n) | O(nยฒ) | O(nยฒ) | O(1) | โ |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | โ |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | โ |
* Quick Sort worst case: occurs with a bad pivot choice on already-sorted or reverse-sorted input (e.g., always picking the last element as pivot). Random pivot selection reduces this to O(n log n) with very high probability. Java's dual-pivot quicksort in
Arrays.sort achieves O(n log n) practically with O(log n) stack space.
Space Complexity Note
Merge sort requires O(n) auxiliary space for the merge buffer. Quick sort uses O(log n) stack space for recursion. Heap sort is the only comparison sort achieving O(n log n) worst-case with O(1) extra space. Radix sort trades time linearity for O(n+k) auxiliary space (output array + counting buckets).
06
Section Six ยท Decision Guide
When to Use Sorting
Use Merge Sort When
- You need a stable sort guaranteed O(n log n)
- Sorting linked lists (no random-access needed)
- External sorting (data larger than RAM)
- Counting inversions via the merge step
Use Quick Sort When
- In-practice fastest for arrays of primitives
- Memory is constrained โ only O(log n) stack space
- Stability not required and average case is fine
Use Heap Sort When
- Need worst-case O(n log n) + O(1) space
- Partial sort: finding top-K elements
- Real-time systems needing predictable performance
Use Radix/Counting Sort When
- Keys are integers with bounded range (k โช n)
- You need linear O(n) time instead of O(n log n)
- Strings with fixed-length keys
Algorithm Decision Table
| Scenario | Recommended | Why |
|---|---|---|
| General-purpose array sort | Quick Sort (random pivot) | Best cache performance, O(n log n) average |
| Need stable sort | Merge Sort / Timsort | Stable, O(n log n) guaranteed |
| Memory critical, no stability | Heap Sort | O(1) space, O(n log n) worst |
| Nearly-sorted input (< 10% disorder) | Insertion Sort / Timsort | O(n) on almost-sorted data |
| Integer keys, small range k < 100k | Counting Sort | O(n+k) linear |
| Integer keys, large but bounded | Radix Sort | O(nk) linear in digit count |
| Java production code | Arrays.sort / Collections.sort | Dual-pivot quicksort (primitives), Timsort (objects) |
โ Never use bubble or selection sort in production or interviews unless the problem explicitly asks to implement a naive O(nยฒ) sort for educational purposes.
07
Section Seven ยท Interview Practice
LeetCode Problems
Sorting problems in interviews test custom comparators, divide-and-conquer thinking, and recognising when sorting unlocks a two-pointer or greedy solution. Many "hard" problems become medium after sorting the input.
- Easy#912 โ Sort an Array โ Implement merge sort or heap sort from scratch without using built-in sort.
- Easy#88 โ Merge Sorted Array โ Merge two sorted arrays in-place from the back to avoid O(n) shifts.
- Medium#56 โ Merge Intervals โ Sort by start time, then greedily merge overlapping intervals.
- Medium#75 โ Sort Colors โ Dutch National Flag: 3-way partition in O(n) time, O(1) space.
- Medium#179 โ Largest Number โ Custom comparator: compare ab vs ba as strings to build the largest concatenation.
- Medium#148 โ Sort List โ Merge sort on a linked list; O(n log n) time, O(log n) stack space.
- Medium#324 โ Wiggle Sort II โ Sort then interleave larger elements at odd indices, smaller at even.
- Hard#315 โ Count of Smaller Numbers After Self โ Modified merge sort counts inversions during the merge step.
- Hard#493 โ Reverse Pairs โ Merge sort variant: count pairs where arr[i] > 2 * arr[j] during merge.
- Hard#4 โ Median of Two Sorted Arrays โ Binary search on partition: O(log(min(m,n))) โ no sort needed.
Interview Pattern: When you see "find pairs", "count inversions", or "merge intervals" โ think sorting first. A custom
Comparator or sorting key often reduces an O(nยฒ) brute force to O(n log n). Always ask: "would sorting the input first make this problem easier?"