The idea behind the

*insertion sort*is to loop over positions in the array, starting with index 1. Each element at the given index needs to be inserted into the correct place in the array.Although it is one of the elementary sorting algorithms with O(n

^{2}) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

{

if(arr == NULL || len <= 1)

return;

for(int i = 1; i < len; ++i)

{

int key = arr[i];

int j = i - 1;

for(; j >= 0 && arr[j] > key; --j)

arr[j+1] = arr[j];

arr[j + 1] = key;

}

}

**Implementation:****void insertionSort(int *arr, int len)**

{

if(arr == NULL || len <= 1)

return;

for(int i = 1; i < len; ++i)

{

int key = arr[i];

int j = i - 1;

for(; j >= 0 && arr[j] > key; --j)

arr[j+1] = arr[j];

arr[j + 1] = key;

}

}

**Complexity:**O(n^{2})