 # Insertion Sort

Insertion sort is based on the idea of consuming one element from unsorted array and inserting it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

### Example:

To understand the insertion sort, lets consider an unsorted array [23, 1, 10, 5, 2] and discuss each step taken to sort the array in ascending order. In every pass, one element is taken from the unsorted array and inserted it at the correct position in the sorted array.

First Pass: The whole array is unsorted array and 23 is taken to be inserted into the sorted array. As 23 is the first element of sorted array and has no elements to be compared with, it remains at its position.

Second Pass: 1 is the taken from unsorted array to insert into sorted array. It is compared with all elements of sorted array and found that 23 is the only number which is greater than 1. 1 is inserted into the sorted array and position of 23 is shifted by one place in the array. This resulted into increasing the length of sorted array by one and decreasing the length of unsorted array by one.

Third Pass: 10 is taken from the unsorted array and compared with all elements of sorted array. 23 is the only number in the sorted array which is greater than 10. 10 is inserted into the sorted array and position of 23 is shifted by one place in the array.

Fourth Pass: 5 is compared with all elements of sorted array and it is found that 10 and 23 are the numbers which need to be shifted by one place to insert 5 into the sorted array.

Fifth Pass: To insert 2 into the sorted array, 5, 10 and 23 are shifted by one place. ## Implementation of Insertion Sort

```# function for insertion sort
def insertionsort(MyList):
for i in range(len(MyList)):
curr = MyList[i]
j = i-1
while j >= 0 and curr < MyList[j] :
MyList[j + 1] = MyList[j]
MyList[j] = curr
j = j - 1

# test insertion sort code
MyList = [1, 10, 23, 50, 4, 9, -4]
print("Original List")
for i in MyList:
print(i, end=" ")
print("\n")

insertionsort(MyList)
print("Sorted List")
for i in MyList:
print(i, end=" ")
```

Output

```Original List
1 10 23 50 4 9 -4

Sorted List
-4 1 4 9 10 23 50
```

```public class MyClass {
// function for insertion sort
static void insertionsort(int Array[]) {
int n = Array.length;
for(int i=0; i<n; i++)
{
int curr = Array[i];
int j = i - 1;
while(j >= 0 && curr < Array[j])
{
Array[j + 1] = Array[j];
Array[j] = curr;
j = j - 1;
}
}
}

// function to print array
static void PrintArray(int Array[])
{
int n = Array.length;
for (int i=0; i<n; i++)
{
System.out.print(Array[i] + " ");
}
System.out.println();
}

//test insertion sort code
public static void main(String[] args) {
int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
System.out.println("Original Array");
PrintArray(MyArray);

insertionsort(MyArray);
System.out.println("\nSorted Array");
PrintArray(MyArray);
}
}
```

Output

```Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50
```

```#include <iostream>
using namespace std;

// function for insertion sort
static void insertionsort(int Array[], int n)
{
for(int i=0; i<n; i++)
{
int curr = Array[i];
int j = i - 1;
while(j >= 0 && curr < Array[j])
{
Array[j + 1] = Array[j];
Array[j] = curr;
j = j - 1;
}
}
}

// function to print array
static void PrintArray(int Array[], int n)
{
for (int i=0; i<n; i++)
{
cout<<Array[i]<<" ";
}
cout<<"\n";
}

// test insertion sort code
int main (){
int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
int n = sizeof(MyArray) / sizeof(MyArray);
cout<<"Original Array\n";
PrintArray(MyArray, n);

insertionsort(MyArray, n);
cout<<"\nSorted Array\n";
PrintArray(MyArray, n);
return 0;
}
```

Output

```Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50
```

```#include <stdio.h>

// function for insertion sort
static void insertionsort(int Array[], int n)
{
for(int i=0; i<n; i++)
{
int curr = Array[i];
int j = i - 1;
while(j >= 0 && curr < Array[j])
{
Array[j + 1] = Array[j];
Array[j] = curr;
j = j - 1;
}
}
}

// function to print array
static void PrintArray(int Array[], int n)
{
for (int i=0; i<n; i++)
{
printf("%i ",Array[i]);
}
printf("\n");
}

// test insertion sort code
int main (){
int MyArray[] = {1, 10, 23, 50, 4, 9, -4};
int n = sizeof(MyArray) / sizeof(MyArray);
printf("Original Array\n");
PrintArray(MyArray, n);

insertionsort(MyArray, n);
printf("\nSorted Array\n");
PrintArray(MyArray, n);
return 0;
}
```

Output

```Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50
```

```using System;

namespace MyApplication {
class MyProgram {
// function for insertion sort
static void insertionsort(int[] Array)
{
int n = Array.Length;
for(int i=0; i<n; i++)
{
int curr = Array[i];
int j = i - 1;
while(j >= 0 && curr < Array[j])
{
Array[j + 1] = Array[j];
Array[j] = curr;
j = j - 1;
}
}
}

// function to print array
static void PrintArray(int[] Array)
{
int n = Array.Length;
for (int i=0; i<n; i++)
{
Console.Write(Array[i] + " ");
}
Console.Write("\n");
}

// test insertion sort code
static void Main(string[] args) {
int[] MyArray = {1, 10, 23, 50, 4, 9, -4};
Console.Write("Original Array\n");
PrintArray(MyArray);

insertionsort(MyArray);
Console.Write("\nSorted Array\n");
PrintArray(MyArray);
}
}
}
```

Output

```Original Array
1 10 23 50 4 9 -4

Sorted Array
-4 1 4 9 10 23 50
```

### Time Complexity:

Insertion sort takes maximum time if the array is in the reverse order and minimum time when the array is already sorted. In worst case scenario every element is compared with all other elements. Therefore, for N elements there will be comparison hence the time complexity of insertion sort is O(N²).