We go over some sorting algorithms which are in the HKOI syllabus.

Bubble Sort

This is an in-place sorting algorithm that only makes use of adjacent swaps. In the $k$'th iteration, the $k$'th largest element "bubbles" up to its correct position, hence the name.

In each iteration, we go through the array, comparing adjacent elements and swap them if they're not in ascending order. Since we know $a[n-k..n-1]$ is in correct position after the $k$'th iteration, the following code is optimized to eliminate unnecessary comparisons.

for (int p = 0; p < n - 1; p++) {
    for (int i = 0; i < n - p - 1; i++) {
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
        }
    }
}

Time complexity: $O(n^2)$

Selection Sort

This is an in-place sorting algorithm. We maintain a sorted prefix, eventually it grows into the size of the array so the array gets sorted.

We first select the minimum element in $a[0..n-1]$ and swap it with $a[0]$. Then we select the minimum element in $a[1..n-1]$ and swap it with $a[1]$. In the $k$'th iteration, the $k$'th smallest element gets put into the correct position in the eventually sorted array.

for (int i = 0; i < n - 1; i++) {
    // we want a[k] to be the smallest element in a[i..n-1]
    int k = i;
    for (int j = i + 1; j < n; j++) {
        if (a[j] < a[k]) k = j;
    }
    swap(a[i], a[k]);
}

Time complexity: $O(n^2)$

Merge Sort

This is a divide-and-conquer sorting algorithm which makes heavy use of the "merging sorted arrays" algorithm. The idea is that we divide the unsorted array into two equal parts, sort each of them, and then combine them into a sorted array using that algorithm.

Divide and conquer is a problem-solving technique: we divide a problem into smaller subproblems, solve each of them individually, then combine them to form a solution to the problem. We do this recursively and set base cases for which the answer is trivial.

For merge sort, the base case is sorting an array consisting of one element. But an array with one element is necessarily sorted.

The following is pseudocode for merge sort:

mergeSort(a):
    if length of a is 1:
        return a
    split a into two roughly equal subarrays b and c
    b = mergeSort(b)
    c = mergeSort(c)
    a = mergeSortedArrays(b, c)
    return a

Time complexity: $O(n \log n)$

Some adjectives to describe sorting algorithms

• In-place: a sorting algorithm that modifies the given array directly - usually, it does not need to create auxiliary arrays for processing.
• Stable: if $a = b$ in the original array, and $a$ comes before $b$ in the original array, then $a$ will come still before $b$ after a stable sorting algorithm is applied.
  • Selection sort is not stable, but bubble sort and merge sort are stable.