Notes › DSA
Sorting Algorithms
Sorting puts elements in order. In interviews you rarely write a sort from scratch for a real problem — you call sort() — but you must know how the main algorithms work, their complexity and their trade-offs.
Watch each one run step by step in the Codify visualizer.
Comparison table
| Algorithm | Best | Average | Worst | Space | Stable | Idea |
|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | ✅ | swap neighbours |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ❌ | pick the minimum |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | ✅ | insert into sorted part |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | divide, sort, merge |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | partition around a pivot |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | build heap, extract max |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ | count each value (small range) |
| Radix | O(d·(n + b)) | — | — | O(n + b) | ✅ | sort digit by digit |
Stable = equal elements keep their original order (matters when sorting records by one field after another).
Insertion sort — great for small or nearly sorted data
void insertionSort(vector<int>& a) {
for (int i = 1; i < a.size(); i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}
Merge sort — divide and conquer
Split in half, sort both halves recursively, merge the two sorted halves. Recurrence T(n) = 2T(n/2) + O(n) → O(n log n) always.
void merge(vector<int>& a, int l, int m, int r) {
vector<int> tmp;
int i = l, j = m + 1;
while (i <= m && j <= r) tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]); // <= keeps it stable
while (i <= m) tmp.push_back(a[i++]);
while (j <= r) tmp.push_back(a[j++]);
for (int k = 0; k < tmp.size(); k++) a[l + k] = tmp[k];
}
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);
}
Bonus: count inversions by counting, during the merge, how many left elements are bigger than a[j].
Quick sort — partition around a pivot
Pick a pivot, move smaller elements left and larger right (Lomuto/Hoare partition), recurse on both sides.
int partition(vector<int>& a, int lo, int hi) {
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) swap(a[i++], a[j]);
swap(a[i], a[hi]);
return i;
}
void quickSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
Worst case O(n²) when the pivot is always the smallest/largest (e.g. already sorted input with the last element as pivot). A random pivot makes that extremely unlikely. In practice quick sort is often fastest (in-place, cache friendly).
Quickselect uses the same partition to find the k-th smallest element in O(n) average.
Counting sort — when values are small
void countingSort(vector<int>& a, int maxVal) {
vector<int> cnt(maxVal + 1, 0);
for (int x : a) cnt[x]++;
int idx = 0;
for (int v = 0; v <= maxVal; v++) while (cnt[v]--) a[idx++] = v;
}
Not comparison-based, so it beats the O(n log n) lower bound — but only for a small range of integers.
Library sorts
| Language | Call | Algorithm |
|---|---|---|
| C++ | sort(a.begin(), a.end()) |
Introsort (quick + heap + insertion), not stable |
| C++ | stable_sort(...) |
merge-sort based, stable |
| Java | Arrays.sort(int[]) |
dual-pivot quicksort |
| Java | Collections.sort(list) / objects |
TimSort, stable |
| Python | sorted(), list.sort() |
TimSort, stable |
Custom order in C++:
sort(v.begin(), v.end(), [](const pair<int,int>& x, const pair<int,int>& y) {
if (x.second != y.second) return x.second > y.second; // by second, descending
return x.first < y.first; // then by first, ascending
});
Which one when?
- Small or nearly sorted → insertion.
- Guaranteed O(n log n), stable, linked lists, external sorting → merge.
- General in-memory arrays → quick (randomised) / library sort.
- O(1) extra space with guaranteed O(n log n) → heap.
- Small integer range → counting / radix.
Interview one-liners
- Lower bound for comparison sorting is Ω(n log n).
- Merge sort is preferred for linked lists (no random access needed, O(1) extra space with pointers).
- Quick sort's worst case is O(n²); merge sort's needs O(n) extra space.
- Practise sorting-based problems in the Arrays section: merge intervals, sort colors (Dutch national flag), kth largest element.