# Insertion Sort

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(n2) 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(n2) 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