Heapsort is another very efficient sorting algorithm. The time it runs is O(nlgn), and you cant get better than that.

The data structure used in this sorting algorithm is the Heap. A Binary Tree in which every parent is bigger or equal to his children.

Heaps can be implemented in many different ways, using arrays or Dynamic Structures.

The sub-routines neccessary to maintain a heap:

Note: The following procedures assume that the heap is stored inside an Array.


These three fundamental procedures will return the parent, the left child or the right child of the I node. They can return the number of the cell in the array in which the value is stored, or a pointer for that node. Depends on how you are implementing the heap.

// A is either the array that stores the heap and I is the index of the node.
// This recursive procedure assumes that the sub-trees of I are heaps, but A(i) could be smaller than one of the nodes in these sub-trees and fixes the problem.
// The running time of Heapify is O(nlgn)
  if l<=Heapsize(A) and A(l)>A(i) then
     largest<--l else
  if r<=Heapsize(A) and A(r)>A(largest) then
  if largest <> i then

//Takes a regular array and makes a heap out of it by heapifying all the non-leaf nodes.
// The running time of Buildheap is O(nlgn)
 for i<--Parent(A(Heapsize(A)) downto 1
      do Heapify(A,i)

And finally, the Heapsort algorithm. First, the Algorithm turns the array to a heap, and then, since the first node is the biggest it replaces it with the last node and decreases the heap size by one. Now the biggest number is in the correct spot, and the process repeats.

// The running time of Heapsort is O(nlgn)
 for i<--length(A) downto 2
     do A(1)<-->A(i)

Note: These algorithms can be easily changed if you prefer to implement heaps using dynamic structures.