# heapifyfor i = n/2:1, sink(a,i,n)→ invariant: a[1,n] in heap order# sortdownfor i = 1:n, swap a[1,n-i+1] sink(a,1,n-i)→ invariant: a[n-i+1,n] in final positionend# sink from i in a[1..n]function sink(a,i,n):# {lc,rc,mc} = {left,right,max} child indexlc = 2*i if lc > n, return# no childrenrc = lc + 1 mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc if a[i] >= a[mc], return# heap orderedswap a[i,mc] sink(a,mc,n)

- Not stable
- O(1) extra space (see discussion)
- O(n·lg(n)) time
- Not really adaptive

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

The first loop, the Θ(n) "heapify" phase, puts the array into heap order. The second loop, the O(n·lg(n)) "sortdown" phase, repeatedly extracts the maximum and restores heap order.

The sink function is written recursively for clarity. Thus, as shown, the code requires Θ(lg(n)) space for the recursive call stack. However, the tail recursion in sink() is easily converted to iteration, which yields the O(1) space bound.

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.

- Click on above to restart the animations in a row, a column, or the entire table.
- Click directly on an animation image to start or restart it.
- Click on a problem size number to reset all animations.

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

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

*Programming Pearls*
by Jon Bentley.
Addison Wesley, 1986.

*Quicksort is Optimal*
by Robert Sedgewick
and Jon Bentley,
Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code and Discussion.

*Bubble-sort with Hungarian ("Csángó") folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

*Select-sort with Gypsy folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.