Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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?

Interview one-liners

More DSA notes