Sorting Algorithms

Once you have a basic understanding of sorting algorithms, make sure to check out https://www.youtube.com/watch?v=kPRA0W1kECg, it is a sorting algorithm and musical masterpiece!

Comparison Sorts

Comparison sorts are limited by a lower bound of $\mathcal{O}(n\log{n})$.

Integer Sorts

Data is indexed by an integer key. Integer sorts are usually faster than comparison sorts.

Counting Sort

• Type: Integer
• Style: Out-of-place
• Worst-case Performance: $\mathcal{O}(n + k)$
• Average-case Performance: $\mathcal{O}(n + k)$
• Best-case Performance: $\mathcal{O}(n + k)$
• Stability: Stable

where $n$ is the number of element in the array and $k$ is a number such that all keys are in the range $0..k-1$.

1. Loop over every element, counting the number of times each particular integer key occurs with the array.
2. Determine, for each distinct key, the starting position in the output array for each element having that key.
3. Iterate over all the elements once more, moving each element into it’s sorted position in the output array.

Insertion Sort

• Type: Comparison
• Style: In place
• Worst-case Performance: $\mathcal{O}(n^2)$ comparisons, $\mathcal{O}(n^2)$ swaps
• Average-case Performance: $\mathcal{O}(n^2)$ comparisons, $\mathcal{O}(n^2)$ swaps
• Best-case Performance: $\mathcal{O}(n)$ comparisons, no swaps
• Stability: Stable

Insertion sort builds the final sorted array one element at a time. It takes the first element from the right-hand side unsorted array, and compares it with each element in the sorted array (starting from the right-most element). If the new element is less than the compared element, it performs a swap.

Insertion sort is really quick for small arrays, even faster than quicksort. The threshold for a faster runtime with insertion sort depends on the language and machine it is running on, but is typically when less or equal to 10 elements.

Insertion sort is very similar to selection sort, but has one distinct advantage. Whilst selection sort must compare every unsorted element to find the next smallest, insertion sort on needs to keep comparing the next element to be sorted until it has found where it needs to insert it in the array.

An example in C:

void insertion_sort(int arr[], int length)
{
    for (int i = 1; i < length; i++) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

An example in C++:

void insertion_sort(std::vector<int>& array) {
    for (auto it = array.begin(), end = array.end(); it != end; ++it) {
        // 1. Search
        auto const insertion_point =
            std::upper_bound(array.begin(), it, *it);

        // 2. Insert
        std::rotate(insertion_point, it, it + 1);
    }
}

Merge Sort

Merge sort splits an array into sub-arrays, sorts each sub-array, and then merges the arrays back together.

The merge algorithm: Remove the element from the array which has the smaller first element and append it to the output array.

Selection Sort

1. Iterates through the unsorted section of the array (which will be the entire array at the start, finds the lowest value.
2. Swaps this element with the far left element of the unsorted array (at the start, this will be the first element).
3. This element on the far left of the unsorted section now belongs to the sorted section of the array. Go back to step 1.