Advanced Sorting

Heap Sort — O(N log N)

No additional array required.

Algorithm Steps

1. Make the array you want to sort on Heap (Heapify) — O(N)

func buildMaxHeap(_ n: Int) {
    for i in (1...(n / 2)).reversed() {
        maxHeapify(i, n)
    }
}

2. In the heap, change the maximum value (root node) to the last value.
3. The size of the heap is assumed to be reduced by one. That is, the last value is not considered part of the heap.
4. Heapify for the root node.
5. Repeat steps 2 to 4.

func heapSort(_ n: Int) {
    buildMaxHeap(n)
    for i in (1...n).reversed() {
        let temp = data[1]
        data[1] = data[i]
        data[i] = temp
        maxHeapify(1, i - 1)
    }
}

Radix Sort — O(d × (n + k))

Default assumption: number of values are n and d-digit integers.

We sort from the last digit. Each digit is sorted by a stable sorting (counting sort, bucket sort) algorithm.

func radixSort(_ array: inout [Int]) {
    let radix = 10  // Here we define our radix to be 10
    var done = false
    var index: Int
    var digit = 1  // Which digit are we on?

    while !done {  // While our sorting is not completed
        done = true  // Assume it is done for now
        var buckets: [[Int]] = []

        // Our sorting subroutine is bucket sort,
        // so let us predefine our buckets
        for _ in 1...radix {
            buckets.append([])
        }

        for number in array {
            index = number / digit  // Which bucket will we access?
            buckets[index % radix].append(number)
            if done && index > 0 {
                // If we aren't done, continue to finish,
                // otherwise we are done
                done = false
            }
        }

        var i = 0
        for j in 0..<radix {
            let bucket = buckets[j]
            for number in bucket {
                array[i] = number
                i += 1
            }
        }

        digit *= radix  // Move to the next digit
    }
}