Problem Statement

Heapsort is an in-place sorting algorithm with worst case and average complexity of   O(n logn). The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element. We repeatedly "remove" the maximal element from the heap, thus building the sorted list from back to front. A heap sort requires random access, so can only be used on an array-like data structure. Pseudocode:

Write a function to sort a collection of integers using heapsort.

Let's start with the solution:

fcn heapSort(a){  // in place
   n := a.len();
   foreach start in ([(n-2)/2 .. 0,-1])
      { siftDown(a, start, n-1) }
   foreach end in ([n-1 .. 1,-1]){
      a.swap(0, end);
      siftDown(a, 0, end-1);
   }
   a
}

fcn siftDown(a, start, end){
   while((child := start*2 + 1) <= end){
      if(child < end and a[child]
      if(a[start] >= a[child]) return();
      a.swap(start, child);
      start = child;
   }
}

heapSort(L(170, 45, 75, -90, -802, 24, 2, 66)).println();
heapSort("this is a test".split("")).println();