Why it matters:
- Enables binary search
- Simplifies deduplication
- Improves cache locality
- Makes many problems _dramatically easier_
Big Picture: How Sorting Algorithms Differ
Sorting algorithms mainly differ by:
- Time complexity (best / average / worst)
- Space usage (in-place vs extra memory)
- Stability (keep equal elements’ order or not)
- Strategy (comparison-based vs non-comparison)
Bubble Sort
Idea: Repeatedly swap adjacent elements if they’re in the wrong order.
[5, 3, 4]
→ [3, 5, 4]
→ [3, 4, 5]
- Time: O(n²)
- Space: O(1)
- Stable: ✅
- Use case: ❌ Mostly educational
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Compare 5 & 3 → swap
[ 3 | 5 | 4 | 1 ]
Compare 5 & 4 → swap
[ 3 | 4 | 5 | 1 ]
Compare 5 & 1 → swap
[ 3 | 4 | 1 | 5 ] ← 5 fixed
Compare 3 & 4 → ok
[ 3 | 4 | 1 | 5 ]
Compare 4 & 1 → swap
[ 3 | 1 | 4 | 5 ] ← 4 fixed
Compare 3 & 4 → ok
[ 3 | 4 | 1 | 5 ]
Compare 4 & 1 → swap
[ 3 | 1 | 4 | 5 ] ← 4 fixed
Compare 3 & 1 → swap
[ 1 | 3 | 4 | 5 ]
Selection Sort
Idea: Select the smallest element and place it at the beginning.
[5, 3, 4]
→ select 3 → [3, 5, 4]
- Time: O(n²)
- Space: O(1)
- Stable: ❌
- Predictable swaps, but still slow
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) {
minIdx = j;
}
}
swap(a[i], a[minIdx]);
}
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Scan → min = 1
Swap with first element
[ 1 | 3 | 4 | 5 ]
Remaining: [ 3 | 4 | 5 ]
Min = 3 → already in place
Remaining: [ 4 | 5 ]
Min = 4 → already in place
Insertion Sort
Idea: Insert each element into its correct position in the sorted part.
[3 | 5, 4]
→ insert 4 → [3, 4, 5]
- Time: O(n²) worst, O(n) best
- Space: O(1)
- Stable: ✅
- Excellent for small or nearly sorted arrays
void insertionSort(vector<int>& a) {
int n = a.size();
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Sorted: [ 5 ]
Insert 3
Shift 5 →
[ 3 | 5 | 4 | 1 ]
Insert 4 into [3 | 5]
Shift 5 →
[ 3 | 4 | 5 | 1 ]
Insert 1
Shift 5 → 4 → 3 →
[ 1 | 3 | 4 | 5 ]
Merge Sort
Idea: Divide → sort → merge.
[5,3,4,1]
→ [5,3] [4,1]
→ [3,5] [1,4]
→ [1,3,4,5]
- Time: O(n log n) always
- Space: O(n)
- Stable: ✅
- Used in external sorting, linked lists
void merge(vector<int>& a, int l, int m, int r) {
vector<int> left(a.begin() + l, a.begin() + m + 1);
vector<int> right(a.begin() + m + 1, a.begin() + r + 1);
int i = 0, j = 0, k = l;
while (i < left.size() && j < right.size()) {
if (left[i] <= right[j]) a[k++] = left[i++];
else a[k++] = right[j++];
}
while (i < left.size()) a[k++] = left[i++];
while (j < right.size()) a[k++] = right[j++];
}
void mergeSort(vector<int>& a, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Divide
[ 5 | 3 ] [ 4 | 1 ]
[ 5 ] [ 3 ] [ 4 ] [ 1 ]
Merge
[ 5 ] + [ 3 ] → [ 3 | 5 ]
[ 4 ] + [ 1 ] → [ 1 | 4 ]
Final merge
[ 3 | 5 ] + [ 1 | 4 ]
Compare 3 & 1 → take 1
Compare 3 & 4 → take 3
Compare 5 & 4 → take 4
Remaining → 5
[ 1 | 3 | 4 | 5 ]
Quick Sort
Idea: Pick a pivot, partition, recurse.
Pivot = 4
[3,1] 4 [5]
- Time: O(n log n) avg, O(n²) worst
- Space: O(log n) (recursion)
- Stable: ❌
- Fastest in practice (with good pivot)
int partition(vector<int>& a, int low, int high) {
int pivot = a[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (a[j] < pivot) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[high]);
return i + 1;
}
void quickSort(vector<int>& a, int low, int high) {
if (low < high) {
int pi = partition(a, low, high);
quickSort(a, low, pi - 1);
quickSort(a, pi + 1, high);
}
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Pivot = 1
Partition:
Elements < pivot → none
Pivot placed:
[ 1 | 3 | 4 | 5 ]
Recurse on right:
Subarray: [ 3 | 4 | 5 ]
Pivot = 5
[ 3 | 4 ] 5
Final step
[ 3 ] 4
Heap Sort
Idea: Build a heap, extract max repeatedly.
- Time: O(n log n)
- Space: O(1)
- Stable: ❌
- Used when memory must be constant
void heapify(vector<int>& a, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest != i) {
swap(a[i], a[largest]);
heapify(a, n, largest);
}
}
void heapSort(vector<int>& a) {
int n = a.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
for (int i = n - 1; i > 0; i--) {
swap(a[0], a[i]);
heapify(a, i, 0);
}
}
Example
Initial:
[ 5 | 3 | 4 | 1 ]
Build max heap:
5
/ \
3 4
/
1
Extract max:
Swap root with last element
[ 1 | 3 | 4 | 5 ]
Heapify:
4
/ \
3 1
Extract again:
[ 1 | 3 | 4 | 5 ]
Heapify:
3
/
1
Final:
[ 1 | 3 | 4 | 5 ]