- Step 1: a heap is built out of the data
- Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.
The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by chossing a min-heap or mar-heap in the step one.
Complexity: O(n.log n)
