# Insertion Sort

Download Insertion Sort Code : [wpdm_package id=’1315′]

Insertion sort is a quite simple effective sorting algorithm for small data sets.

**Points to remember about Insertion Sort :**

1. More efficient then Selection Sort and Bubble Sort.

2. **Time Complexity** –

i. Worst Case – O(n^{2}) comparisions, swaps – When all the elements are sorted in reverse order i.e. a[1]>a[2]>a[3]>a[4]>a[5]

ii. Best Case – O(n) comparisions, O(1) swaps – When all the elements are already sorted

iii. Average Case – O(n^{2}) comparisions, swaps

3. **Stable** – with equal elements does not change their order.

4. **Inplace** – Always need O(1) additional memeory space whatever be the size of n (size of array).

5. **Online**– Sort the elements as it receives from user.

**Pseudo code : **

[sourcecode language=”c”]

for(i=1 to length[a]-1)

temp=a[i]

j=i-1

while(j>=0 && temp<a[j])

a[j+1]=a[j]

j=j-1

end while

a[j+1]=temp

end for

[/sourcecode]

**How does Insertion Sort Work :**

Suppose our array a is

12 43 1 24 5

Iteration** 1** :

temp=43, we compare 43 with 12 i.e. 12 12 43 1 24 5

Iteration **2** :

temp=1, we compare 1 with 43 i.e. 43>1 so we shift 43

12 ? 43 24 5

Now we compare 1 with 12 i.e. 12>1 so we shift 12 and copy temp=1 at 1st position, After 2nd iteration we get

1 12 43 24 5

Iteration **3** :

temp=24, we compare 24 with 43 i.e. 43>24 so we dhift 43

1 12 ? 43 5

Now we compare 24 with 12 i.e. 12 1 12 24 43 5

Iteration **4** :

temp=5, we compare 5 with 43 i.e. 43>5 so we shift 43

1 12 24 ? 43

Now we compare 5 with 24 i.e. 24>5 so we shift 24

1 12 ? 24 43

Now we compare 5 with 12 i.e. 12>5 so we shift 12

1 ? 12 24 43

Now we compare 5 with 1 i.e 1 1 5 12 24 43