Stand-alone HeapSort implementation in Swift. Uses MaxHeap properties to sort elements in an array.

HeapSort.swift

private func heapify<Element>(_ array: inout [Element], _ count: Int, _ index: Int) where Element: Comparable {
    var largest = index
    let l = 2 * index + 1
    let r = 2 * index + 2
    
    //// Check if left child exists and is greater than parent.
    if l < count && array[index] < array[l] {
        largest = l
    }
    
    //// Check if right child exists and greater than parent.
    if r < count && array[largest] < array[r] {
        largest = r
    }
    
    //// Swap child with parent if child is larger.
    if largest != index {
        array.swapAt(index, largest)
        heapify(&array, count, largest)
    }
}

func heapSort<Element>(_ array: inout [Element]) where Element: Comparable {
    let count = array.count
    
    //// Build MaxHeap.
    for i in stride(from: count, to: -1, by: -1) {
        heapify(&array, count, i)
    }
    
    //// Extract the largest element from MaxHeap
    //// - Largest element swaped with last element in MaxHeap.
    //// - Size of MaxHeap decreases by 1 on each pass.
    //// - Heapify called to restore MaxHeap properties.
    for i in stride(from: count - 1, to: 0, by: -1) {
        array.swapAt(i, 0)
        heapify(&array, i, 0)
    }
}