Heapsort

Heap sort or heapsort is a sorting algorithm. It was presented in 1964, and helped make a data structure known as heap popular. Heapsort divides the input into a sorted and an unsorted region. It then takes the largest element from the unsorted region and inserts it into the sorted region. The unsorted region is kept as a heap, which allows finding the largest element quickly. Heapsort is not stable. It has a worst-case complexity of O(n*log(n)).

Heapsort Media

• 

  An animation of the heapsort algorithm sorting an array of randomized values. Created with: Ruby 1.8.4 and RMagick

• 

  Difference in time complexity between the "siftDown" version and the "siftUp" version.

• 

  An example of heapsort using Williams' heap-construction algorithm.