Animated Sorting Algorithm Demo: Heap Sort

Algorithm

# heapify
for i = n/2:1, sink(i,n)
invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[i,n-i+1]
    sink(1,n-i)
    invariant: a[n-i+1,n] in final position
end
        

Properties

• Not stable
• In place: O(1) extra space
• Ω(n·lg(n)) time
• Basically non-adaptive

Discussion

Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.

In the code above, sink(i,n) sinks element i in a heap that occupies a[1..n]. The first loop puts the array into heap order. The second loop, the "sortdown", repeatedly extracts the maximum and restores heap order. The array is put into heap order using the bottom-up heapify method, which takes Ω(n) time. The sortdown takes Ω(n·lg(n)) time.

Both phases are slightly adaptive, though not in any particularly useful manner. In the nearly sorted case, the heapify phase destroys the original order. In the reversed case, the heapify phase is as fast as possible since the array starts in heap order, but then the sortdown phase is typical. In the few unique keys case, there is some speedup but not as much as in shell sort or 3-way quicksort.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• A red triangle marks the algorithm position.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.