PHP Straight Insertion sort

The key step of any insertion sorting algorithm involves the insertion of an item into a sorted sequence. There are two aspects to an insertion--finding the correct position in the sequence at which to insert the new element and moving all the elements over to make room for the new one.

This section presents the straight insertion sorting algorithm. Straight insertion sorting uses a linear search to locate the position at which the next element is to be inserted.


PHP implementation:

function straightInsertion( $array )
{
 
 for( $i=1; $i < count($array); $i++ )
 {
  $tmp = $array[$i];
  // store current element's value because it
  // will be overwritten if it is not in its place
  
  // loop until current element is smaller than previous.
  // if so replace current with previous.
  for( $j = $i-1; $tmp < $array[$j]; $j-- )
   $array[$j+1] = $array[$j];

  // now we can write current element's value on its position.
  $array[$j+1] = $tmp;
 }

 return $array;
}