Insertion Sort

insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort.

Performance:

Worst case: O(n2)
Average case: O(n2)
Best case: O(n)

 <?php

 function insertionSort(array $array) {
        $length=count($array);
        for ($i=1;$i<$length;$i++) { 
          $element=$array[$i]; //put second element in temp variable to compare from all last elements
          $j=$i; 
               while($j>0 && $element<$array[$j-1]) {
                $array[$j]=$array[$j-1]; //move value to right 
                $j=$j-1; // move key to previous smaller index
                }
            //put the element at index $j
            $array[$j]=$element; //set element to leftmost position till $j is decremented 
            }
        return $array;
    }

   $a=array(22,5,9,7,44,66);
   echo "Initial Array Elements";
   print_r($a);
   $b=insertionSort($a);
   echo "Sorted Array Elements";
   print_r($b);

Initial Array Elements Array ( [0] => 22 [1] => 5 [2] => 9 [3] => 7 [4] => 44 [5] => 66 ) 
Sorted Array Elements Array ( [0] => 5 [1] => 7 [2] => 9 [3] => 22 [4] => 44 [5] => 66 )