PHP Heapsort

Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.

During extraction, the only space required is that needed to store the heap. In order to achieve constant space overhead, the heap is stored in the part of the input array that has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.)

Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array. The remaining prefix of the array stores the unsorted elements.


PHP implementation:

function heapSort( $array )
{
 $right = count( $array )-1;
 $left = (int)($right/2) + 1;
 
 while( $left > 0 )
 {
  $left--;
  sift($array, $left, $right);
 }
 
 while( $right > 0 )
 {
  $tmp = $array[0];
  $array[0] = $array[$right];
  $array[$right] = $tmp;
  $right--;
  
  sift($array, $left, $right);
 }
 
 return $array;
}
function sift( &$array, $left, $right )
{
 $i = $left;
 $j = 2*$i;
 $tmp = $array[$i];
 
 while( $j <= $right )
 {
  if( $j < $right && $array[$j] < $array[$j+1] )
   $j++;
  if( $tmp >= $array[$j] ){
   $array[$i] = $tmp;
   return 0;
  }
  $array[$i] = $array[$j];
  $i = $j;
  $j = 2*$i;
 }
 
 $array[$i] = $tmp;
}