Sorting Algorithms

Why sorting is a rite of passage

Sorting — arranging data in order — is one of the most studied problems in computer science, and a favourite of interviewers because it teaches algorithmic thinking so clearly. We'll build up from simple, slow sorts to a fast, elegant one, and you'll learn why the fast ones are fast.

Bubble sort: the simplest (and slowest)

Bubble sort repeatedly walks through the list, swapping any two neighbours that are out of order. Big values "bubble up" to the end pass by pass:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // swap neighbours
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Two nested loops make this O(n²). It's intuitive and easy to code, but for large data it's painfully slow. Still, every programmer should write it once — it cements how comparison and swapping build a sort.

Selection and insertion sort

Two more O(n²) sorts each teach a different idea. Selection sort repeatedly finds the smallest remaining element and places it next:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr[i], arr[minIndex]);   // C++ has a built-in swap
    }
}

Insertion sort builds the sorted portion one element at a time, inserting each new element into its correct place — exactly how most people sort playing cards in their hand. It's genuinely fast on small or nearly-sorted data, which is why real libraries use it as a sub-step. Knowing each sort's character — not just its Big-O — is what lets you pick the right tool.

Merge sort: divide and conquer

Now the leap to O(n log n). Merge sort uses a powerful strategy called divide and conquer: split the array in half, sort each half (by splitting them further, all the way down to single elements), then merge the sorted halves back together. A single element is already sorted, so the recursion bottoms out cleanly.

void merge(int arr[], int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else                  temp.push_back(arr[j++]);
    }
    while (i <= mid)   temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) arr[left + k] = temp[k];
}

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;          // base case: one element
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);          // sort left half
    mergeSort(arr, mid + 1, right);     // sort right half
    merge(arr, left, mid, right);       // combine them
}

Why merge sort is O(n log n)

Here's the intuition. We split the array in half repeatedly — that's log n levels of splitting (the same halving that made binary search fast). At each level, merging everything back together touches all n elements once. So the total work is n × log n. That O(n log n) is provably the best any comparison-based sort can achieve, and it's the reason merge sort and quick sort power real systems while bubble sort stays in textbooks.

The takeaway: divide and conquer is a superpower

Merge sort matters less as a thing to memorise and more as your first taste of divide and conquer — break a big problem into smaller copies of itself, solve those, combine. This pattern, built on recursion (our chapter after next), powers quick sort, binary search, tree algorithms, and countless interview problems. In practice you'll often just call your language's built-in sort:

#include <algorithm>
vector<int> v = {5, 2, 9, 1, 7};
sort(v.begin(), v.end());   // O(n log n), highly optimised

But understanding what happens inside — and being able to write merge sort on a whiteboard — is exactly what interviews test. Next we move from algorithms to data structures proper, starting with the linked list, where the pointers you learned in C finally shine.