Sorting

Sorting — Bubble, Selection, Merge & Quick Sort with Invariant Analysis

Module 5 — Sorting: Bubble, Selection, Insertion, Merge & Quick Sort Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

1. Sorting Invariants & Classification

Sorting algorithms rearrange elements into non-decreasing order. Every algorithm is characterized by three core trade-offs:

Time Complexity: Quadratic ($O(n^2)$) vs Divide-and-Conquer Linearithmic ($O(n log n)$).
Space Complexity (In-Place vs Extra Space): Does it require auxiliary arrays (Merge Sort $O(n)$) or sort within existing memory (Quick Sort $O(log n)$, Bubble/Insertion $O(1)$)?
Stability: Does it preserve the relative order of elements with equal keys? (Crucial when sorting records with multiple fields, like sorting by last name then first name).

2. Divide-and-Conquer: Merge Sort

Merge Sort recursively divides the array into two halves, sorts each half, and merges the two sorted halves into a single combined array.

void merge(vector<int>& arr, int lo, int mid, int hi) {
    vector<int> temp;
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        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 <= hi) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) arr[lo + k] = temp[k];
}

void mergeSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

Figure 5.1 — Merge Sort: Divide array in halves until base case of size 1, then merge back in sorted order

3. Divide-and-Conquer: Quick Sort & Partitioning

Quick Sort picks a pivot element and partitions the array so that all elements smaller than the pivot sit to its left, and all larger elements sit to its right. The pivot is then in its permanent sorted location.

int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[hi]);
    return i + 1;
}

void quickSort(vector<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);
    }
}

4. Comprehensive Sorting Comparison Matrix

Algorithm	Best Time	Average Time	Worst Time	Space	Stable?	In-Place?
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Yes
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No	Yes
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Yes
Merge Sort	$O(n log n)$	$O(n log n)$	$O(n log n)$	$O(n)$	Yes	No
Quick Sort	$O(n log n)$	$O(n log n)$	$O(n^2)$	$O(log n)$	No	Yes
Heap Sort	$O(n log n)$	$O(n log n)$	$O(n log n)$	$O(1)$	No	Yes

Common Pitfall: Quick Sort degrades to $O(n^2)$ worst-case if you pick the last element as pivot on an already sorted or reverse-sorted array! Always pick a randomized pivot (`lo + rand() % (hi - lo + 1)`) or use median-of-three to guarantee $O(n log n)$ expected runtime.

Practice Sorting MCQs

Master Sorting concepts with timed, competitive MCQs with detailed explanations.

Start Topic Quiz →