Objective

**Insertion Sort ** is a simple algorithm that we use to sort a given sequence of n numbers mostly arrays. It is an efficient algorithm for sorting a small number of elements.

The insertion sort algorithm is an algorithm that is used by people in their everyday life than other algorithms. Take playing cards as an example, we take one card at a time from the pack and insert it into the correct position in our hand. To find the correct position for a card, we compare it with each of the cards already present in hand.

## Algorithm

The concept behind the Insertion sort algorithm is that we remove elements from an unordered set one by one and then insert them into an ordered set in the correct position.

Assume we have two arrays :

- An unsorted array of
**n**elements as input. - A sorted array of input as output.

Now in the beginning, sorted array contains the first element of array and others will be in unsorted array. In each step, the algorithm will take the first element from unsorted array and insert it to correct position in sorted array. When all elements will be moved from unsorted to sorted array, algorithm will stop.

A simple example to illustrate how insertion sort works :

**Input :** {5,2,6,8,4}.

** Output :** {2,4,5,6,8}.

## Complexity analysis

- Best Case : O(n).
- Average Case : O(n2).
- Worst Case : O(n2).

On average Insertion sort’s complexity is O(n2). Best case of Insertion sort comes while sorting an almost sorted arrays which is O(n).

From the point of view of practical application, average case complexity of the insertion sort is not so important as Insertion sort is mostly used in sorting of small arrays. While working with small arrays Insertion sort is one of the fastest algorithms, even faster than **Quick sort**.

## Insertion Sort properties

- Implementation of Insertion sort is very simple.
- Very much efficient for small data sets.
- In practice Insertion sort is more efficient than most of the other simple quadratic (
**O(***n***2****)**) algorithms such as selection sort or bubble sort. - Its Stable, i.e, it does not change the relative order of element with same values.
- In-place, i.e., it only requires a constant amount of additional memory, i.e., O(1).
- Online, i.e., if a new element is added to list during sort then it will get sorted as others.

## PHP implementation of Insertion sort

<br /> <?php</p> <p>/*<br /> *Function for sorting an array with insertion sort algorithms<br /> */</p> <p>function sortInsertion($array) {</p> <p> $sortedArray = array();</p> <p> for ($i = 0 ; $i < count($array); $i++) {</p> <p> $element = $array[$i];<br /> $j = $i;</p> <p> while($j > 0 && $sortedArray[$j-1] > $element) {</p> <p> $sortedArray[$j] = $sortedArray[$j-1];<br /> $j = $j-1;<br /> }<<br /> $sortedArray[$j] = $element;<br /> }<br /> return $sortedArray;<br /> }</p> <p>$unsorted = [5,2,6,8,4];<br /> $val = sortInsertion($unsorted);<br /> print_r($val);</p> <p>?></p> <p>

### Output

`Array ( [0] => 2 [1] => 4 [2] => 5 [3] => 6 [4] => 8 )`

## Step wise explanation of above code

- We have a function named sortInsertion(), which takes an unsorted array as input.
- Now we will iterate through that unsorted array using
**for**loop. - Inside
**for**loop, we will take**i****th****$element**in each iteration and put it into sorted array() in its correct position,**j****th**. - Now to find correct position,
**while**loop is implemented. **while**loop will check if**$element**is greater than**(****j****-1 )****th**element in**$sortedArray**.- If the above condition is met then insert
**$element**in**$sortedArray**at**j****th**position. - If not, then compare it with
**( j-2 )****th**in sorted array if greater then shift**( j-2 )****th**element to right and put**$element**in its place. - If not then repeat the same procedure.
- After iteration is complete and final sorted array, algorithm will terminate.