Sorting Algorithms: Bubble, Selection, Insertion, Merge, Quick and Heap Sort

Terms

• Internal sort: all data fits in main memory. External sort: data is on disk.
• In-place: uses only O(1) extra memory (apart from the recursion stack).
• Stable: equal elements keep their original relative order.

Bubble sort

Repeatedly compare adjacent elements and swap them if they are out of order. After pass i, the i largest elements are in their final places at the end.

for (i = 0; i < n - 1; i++)
    for (j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }

Time: O(n²) (O(n) best case with a "no swaps" flag). Stable, in place.

Selection sort

In each pass, find the minimum of the unsorted part and swap it into the next position.

Trace [64, 25, 12, 22, 11]:

• Pass 1: min 11, swap with 64 → [11, 25, 12, 22, 64]
• Pass 2: min 12 → [11, 12, 25, 22, 64]
• Pass 3: min 22 → [11, 12, 22, 25, 64]
• Pass 4: no change → sorted

Time: O(n²) always; only n − 1 swaps. Not stable.

Insertion sort

Take the next element and insert it into its correct place in the already-sorted left part, shifting larger elements right.

for (i = 1; i < n; i++) {
    key = a[i];
    j = i - 1;
    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
    a[j + 1] = key;
}

Time: O(n²) worst case, O(n) when the data is already nearly sorted. Stable, in place. Good for small arrays.

Merge sort (divide and conquer)

1. Divide the array into two halves.
2. Conquer: sort each half recursively.
3. Combine: merge the two sorted halves into one.

Trace [38, 27, 43, 3, 9, 82, 10]:

• Split into [38, 27, 43, 3] and [9, 82, 10], then down to single elements.
• Merge back: [27, 38], [3, 43] → [3, 27, 38, 43]; [9, 82], [10] → [9, 10, 82]
• Final merge: [3, 9, 10, 27, 38, 43, 82]

T(n) = 2T(n/2) + n = O(n log n) in every case. It needs O(n) extra space for merging. Stable.

Quick sort (divide and conquer)

1. Choose a pivot (for example, the last element).
2. Partition: put the elements smaller than the pivot on its left and the larger ones on its right. The pivot is now in its final position.
3. Recursively quick-sort the left and right parts.

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1, t;
    for (int j = lo; j < hi; j++)
        if (a[j] <= pivot) { i++; t = a[i]; a[i] = a[j]; a[j] = t; }
    t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}

void quickSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

• Average and best case: O(n log n), with balanced partitions.
• Worst case: O(n²), when the pivot is always the smallest or largest (e.g. an already sorted array with the last element as pivot). A random or median-of-three pivot avoids this in practice.

In place (O(log n) stack). Not stable. Usually the fastest sort in practice.

Heap sort

1. Build a max-heap from the array (O(n)).
2. Repeat: swap the root (the maximum) with the last element of the heap, shrink the heap by one, and heapify the root (O(log n)).

Time: O(n log n) in all cases. In place. Not stable.

Shell sort

An improvement on insertion sort: first sort elements that are a gap apart, then reduce the gap (e.g. n/2, n/4, …, 1). Elements move long distances early, so the final insertion sort is fast. Typically about O(n^1.25) to O(n^1.5).

Summary

Exam tip

"Trace quick sort / merge sort on the following data" is a regular 10-mark question. Show every partition or merge step, and finish with the time complexity and why (for example, T(n) = 2T(n/2) + n for merge sort).