heapsort in array · Fleeting Years

heapsort in array · Fleeting Years

Heapsort is one of the algorithms for sorting, with average time complexity $O(n log(n))$ and worst $O(n log(n))$, and space complexity $O(1)$. I think it's kind of interesting, so I write down the Java implementation here. Previously I was familar with the top-down (siftUp()) method, but in this post I write down the buttom-up (siftDown()) way, based on Wikipedia.

Firstly heapify() using siftDown() with time $O(n)$ to build the max heap, then pop the top into the sorted part and siftDown() the heap part to maintain the heap property. Most importantly,

Read full article from heapsort in array · Fleeting Years