Let's write an inplace Heapsort in Swift

Using only extensions, learn how to implement a inplace heapsort, and order your lists in O(n log n).

Photo by chuttersnap on Unsplash

I was really interested on this problem of sorting elements. Sorting with heapsort is fast! But it has a big problem: conventionally you have to build a heap to use a heap sort. In a real world usually you don't have a heap mounted to sort whenever. I just imagined that we could create a heapsort inplace, and instead of dealing with heaps objects, we could still have our simple array, and only transform it in a heap when needed.

First of all, I hope you understand what is a heap, and how the heapsort works. If not, I wrote those two pieces that are potentially a good start to understand this structure and sorting algorithm.

The procedures to create a inplace heapsort

The process will be simple. We'll have a list, we'll transform that list in a heap, and then we'll apply the heapsort. The good news is we'll still use just loops to build these guys, leaving aside any recursive call.

In a quick analysis, the list will be transformed into a heap in O(n log n), the heap will be sorted in O(n log n). So we basically keep our computational complexity. What is good for us, seems that…