## Heapsort, because I haven’t posted in a while

This is heapsort in a Swift playground. I needed a stable sort, so naturally I wrote an… unstable sort.

Of course, you can just use `sort()` or `sorted()`, but if you are inclined to roll your own, the Swifty way to do it is to create an extension. Note that an Array extension with a Generic Where Clause is needed to make element comparisons `> < ==` work.

```//: Playground - noun: a place where people can play

import Cocoa

// var elements = [0, 6, 0, 6, 4, 0, 6, 0, 6, 0, 4, 3, 0, 1, 5, 1, 2, 4, 2, 4]

var elements = [10, 6, 0, 1, 2, 5, 4, 3, 7, 8, 9]

extension Array where Element: Comparable {
func heapSorted() -> Array {
var r = self

func parent(_ i: Int) -> Int {
return ((i+1) / 2) - 1
}

func leftChild(_ i: Int) -> Int {
return ((i + 1) * 2) - 1
}

func rightChild(_ i: Int) -> Int {
return leftChild(i) + 1
}

func descend(i: Int, limit: Int) {
let lindex = leftChild(i)
let rindex = rightChild(i)
if rindex > limit || r[lindex] > r[rindex] {
if lindex <= limit && r[lindex] > r[i] {
(r[lindex],r[i]) = (r[i],r[lindex])
descend(i: lindex, limit: limit)
}
} else if rindex <= limit {
if r[rindex] > r[i] {
(r[rindex],r[i]) = (r[i],r[rindex])
descend(i: rindex, limit: limit)
}
}
}

func maxHeapify() {
let lastParent = parent(r.count - 1)
for i in (0...lastParent).reversed() {
descend(i: i, limit: r.count - 1)
}
}

func sortFromHeap() {
for i in (1..<r.count).reversed() {
(r[0],r[i]) = (r[i],r[0])
descend(i: 0, limit: i-1)
}
}

maxHeapify()
sortFromHeap()

return r
}
}

elements.heapSorted().forEach{print(\$0, terminator: " ")}
print()```

On to writing mergesort (stable).

Sigh.