Sorting algorithms are a part of almost all introductory algorithm courses. Though sorting is a little more complex than what this post may convey, I thought it would be a good way to refresh my concepts on this topic.

Insertion Sort

Insertion Sort works well on smaller data or data that is partially sorted but performs terribly everywhere else on account of its $O(n^{2})$ worst-case time complexity. The algorithm is straight-forward.

InsertionSort(array, size)
    for j:= 2 to size do
        key := array[j]

        i:= j - 1

        while i > 0 and array[i] > key do
            array[i + 1] := array[i]
            i := i - 1

        array[i + 1] := key

    return array

Essentially what is happening is that whenever an element is considered, it is placed in its correct position without considering the elements after it.

The best-case time-complexity is $O(n)$, which happens when the input sequence is already sorted. The reason is evident when we consider that the while loop condition of $array[i] > key$ never holds, and therefore each element is considered only one.

It is an in-place and stable sorting technique.


MergeSort

MergeSort(array, size)
    start := 0
    end := size - 1

    MergeSortRecursive(array, start, end)


Merge(array, start, mid, end)
    size1 := mid - start + 1
    size2 := end - mid

    arrayleft = array[start ... mid]
    arrayright = array[mid + 1 ... end]

    i := 0
    j := 0

    for k := start to (end - 1) do
        if (arrayleft[i] <= arrayright[j])
        then do
            array[k] = arrayleft[i]
            i := i + 1
        else
            array[k] = arrayright[j]
            j := j + 1

    // It is very likely that one of i or j will reach size1 or size2
    before the other. Once that condition is reached, all remaining elements
    of `array` will be those of the unended subarray. 

MergeSortRecursive(array, start, end)
    if start < end then do
        mid := floor((start + end) / 2)
        MergeSortRecursive(array, start, mid)
        MergeSortRecursive(array, mid + 1, end)
        Merge(array, start, mid, end)



QuickSort

QuickSort is one of the best general sorting algorithms. It has a worst-case time complexity of $O(nlog(n))$.

It uses a partition based approach. Fundamentally, the collection of data is partitioned about a particular point, also called a pivot. There are several ways of arriving at this point, but for the purpose of this post, we will consider the last element as the pivot. Following that, this point will be inserted in a location which satisfies the invariant that any element to the left of the pivot are smaller than it and those after it are greater.

One that is done, a simple divide and conquer approach is used to sort the collection.

Quicksort can be implemented as shown below.

Partition (array, start, end)
    x := array[end]
    i := start - 1

    for j := p to end - 1 do
        if array[j] <= x
        then do
            i := i + 1
            array[i] <--> array[j]

    array[i + 1] <--> array[end]

    return i + 1

QuickSort(array, start, end)
    if start < end
    then do
        pivot = Partition(array, start, end)

        QuickSort(array, start, pivot - 1)
        QuickSort(array, pivot + 1, end)