# Implement Insertion Sort with Time complexity Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The procedure of the insertion sorting algorithm is that the given array is divided into two parts. There are the sorted array and unsorted array. We select a value from the unsorted part and then put it on the sorted side.

## Algorithm of Insertion Sort

To sort an array of size n in ascending order:
1: Iterate from arr to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

##### Read More : How to implement interpolation search using recursion

Let’s see the following code.

``````
def insertion_sort_asc(A, n):
for i in range(1, n):
temp = A[i]
j = i-1
while j >= 0 and A[j] >= temp:
A[j+1] = A[j]
j -= 1
A[j+1] = temp``````

Well, this function takes two parameters. The first parameter is our given array and the second parameter is the size of the array. Inside the function, we have to execute a loop from one index to the previous index of array length. Then take a variable and store the value of A[i]. After then take another variable and store i – 1.

Well, now you have to execute another loop, and its conditions are `j `value is greater than or equal to zero as well as A[j] value is greater than temp value. After then exchange the value of A[j+1] with A[j]. Then decrease the length of j. Finally, out the second loop and exchange the value of A[j+1] with temp. And our work has been done.

The time complexity of insertion sort is O(n^2).

## Full Code in Python

```def insertion_sort_asc(A, n):
for i in range(1, n):
temp = A[i]
j = i-1
while j >= 0 and A[j] >= temp:
A[j+1] = A[j]
j -= 1
A[j+1] = temp

def insertion_sort_dsc(A, n):
for i in range(1, n):
temp = A[i]
j = i-1
while j >= 0 and A[j] <= temp:
A[j+1] = A[j]
j -= 1
A[j+1] = temp

arr = [5, 1, -8, 4, 2, 3]
len = len(arr)

print(arr)
insertion_sort_dsc(arr, len)
print(arr)
```

## Full Code of Insertion sort in C++

``````#include <bits/stdc++.h>
using namespace std;

void print_array(int A[], int n)
{
cout << endl;
for (int i = 0; i < n; i++)
{
cout << A[i] << " ";
}
cout << endl;
}
void selection_sort_asc(int A[], int n)
{
for (int i = 1; i < n; i++)
{
int temp = A[i];
int j = i - 1;

while (j >= 0 && A[j] >= temp)
{
A[j + 1] = A[j];
j--;
}

A[j + 1] = temp;
}
}
void selection_sort_dsc(int A[], int n)
{
for (int i = 1; i < n; i++)
{
int temp = A[i];
int j = i - 1;

while (j >= 0 && A[j] < temp)
{
A[j + 1] = A[j];
j--;
}

A[j + 1] = temp;
}
}
int main()
{
int A[] = {3, 4, 1, 2, 10};
int n = 5;
print_array(A, n);
selection_sort_asc(A, n);
print_array(A, n);
return 0;
}
``````
##### Read More Artical : Implement Quick Sort using Python and C++ & Time complexity 