## Insertion Sort algorithm – PHP implementation

**Algorithm:**

- Remove the element from the input array.
- Check to the left where is correct position for this element and move all elements to right with one step if those are bigger than element
- Insert the element in correct position

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array. Insertion sort’s advantage is that it only scans as many elements as needed to determine the correct location of the (k+1)st element, while selection sort must scan all remaining elements to find the absolute smallest element.

However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems.

**Performance:**

- Worst case: O(n
^{2}) - Average case: O(n
^{2}) - Best case: O(n)

**PHP implementation** (function from a larger sort Class):

/**Function for sorting an array with insertion sort algorithm. * * @param array $array * @return array */ public static function insertionSort(array $array) { $length=count($array); for ($i=1;$i<$length;$i++) { $element=$array[$i]; $j=$i; while($j>0 && $array[$j-1]>$element) { //move value to right and key to previous smaller index $array[$j]=$array[$j-1]; $j=$j-1; } //put the element at index $j $array[$j]=$element; } return $array; }

**Bibliography:**

**Introduction to Algorithms**– Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein**Algorithms**– Robert Sedgewick- http://en.wikipedia.org/wiki/Insertion_sort