# insertion sort

It is a simple sorting algorithm in which array is split into two parts ,first part is sorted and an another part is unsorted . Values from the unsorted part are picked and placed at the correct position in the sorted part.

**Algorithm**

first divide the array into sorted and unsorted array ,in sorted array only one element is present in the beginning ie. arr[0] (as only one element is always sorted) and in unsorted array the remaining elements from arr[1] to arr[n]

1: Iterate from arr[1] to arr[n] over the unsorted array.

2: store the current element in temp variable now compare the temp variable to all the elements in the sorted array starting from rightmost element

3:if temp is smaller than those elements we move that particular element to right by one position

4: till we find temp greater than any element in sorted array we will continue the above step 3

4: once the temp is greater than any of these elements , we move that element to one position right and place temp in that particular position

lets take an example and see how insertion sort works:

void insertionSort(int arr[], int n) { int temp, j; for (int i = 1; i < n; i++) { temp = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than temp, to one position ahead of their current position */ while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = temp; } }

**Time Complexity:** O(n*2)

**Auxiliary Space: **O(1)