PHP Binary Insertion sort

The straight insertion algorithm presented in the preceding section does a linear search to find the position in which to do the insertion. However, since the element is inserted into a sequence that is already sorted, we can use a binary search instead of a linear search. Whereas a linear search requires Θ(n) comparisons in the worst case, a binary search only requires Θ(logn) comparisons. Therefore, if the cost of a comparison is significant, the binary search may be preferred.


PHP implementation:

function binaryInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  $left = 0;
  $right = $i-1;
  
  // finds the last element with value smaller then current element
  // all elements before the current are sorted
  // so we can find the middle and
  // check only the right(correct) half
  while( $left <= $right )
  {
   $middle = (int)(($left+$right)/2);
   if( $tmp < $array[$middle] )
    $right = $middle - 1;
   else
    $left = $middle + 1;
  }
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $j >= $left; $j-- )
   $array[$j+1] = $array[$j];
  
  $array[$left] = $tmp;
  // now we can write current element's value on its position.
 }

 return $array;
}