# Insertion Sort in Data Structure

Insertion sort is a comparison-based sorting algorithm mostly suited for small datasets. Insertion sort has wide practical implementations. For example, sorting of play cards is an implementation of insertion sort. Arranging randomly arranged answer sheets in the ascending order of roll numbers is also an example of insertion sort.

### What is Insertion Sort?

In insertion sort, there are two lists in the array at every point: A partially sorted list and an unsorted list. Thus, we virtually split the array into sorted and unsorted parts.

Every time we pick up an element from the unsorted array and place it in the partially sorted array. Thus, we insert the elements from an unsorted array at their correct position in the sorted array. That is why the name Insertion. It is not suitable for very large datasets.

Insertion sort is a stable element. The order of duplicate elements is preserved after the sorting is performed.

### Insertion Sort Algorithm

```Step 1: For i = 1 to n-1
Step 2: Set temp = array[i]
Step 3: Set j = i-1
Step 4:  while temp <= array[j]
Set array[j + 1] = array[j]
Set j = j-1
Step 5:  Set array[j + 1] = temp
Step 6: END
```

### Insertion Sort Pseudo-code

```Procedure Insertion_sort(int Arr)
int insert_at_position, insert_value;
for int i = 1 to length.Arr :
insert_value = Arr[i]
insert_at_position = i
while insert_at_position > 0 and Arr[insert_at_position-1] > insert_value:
Arr[insert_at_position] = Arr[insert_at_position-1]
insert_at_position = insert_at_position -1
END while
Arr[insert_at_position] = insert_value
END for
END procedure
```

### Working of Insertion Sort

Let us understand the working of insertion sort with the help of an example. Suppose we wish to sort the elements of the word “TECHVIDVAN” in alphabetical order. Then, we will proceed as follows:

In each iteration, we will bring one element from the unsorted list to the sorted list and place it at its correct position.

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

Iteration 8:

Iteration 9:

Finally, after the 9th iteration, we have got the sorted array.

We need to note here that the insertion sort is a stable sorting algorithm. Thus, the order of duplicates is preserved. Here, we have two duplicate elements- ‘V’. thus, the order of both the ‘V’s will remain the same before and after sorting.

### Insertion Sort Implementation in C

```#include <stdio.h>
void Insertion_sort(int Arr[], int n)
{
for (int position=1; position<size; position++)
{
int val = Arr[position];
int j = position - 1;
while (val < Arr[j] && j >= 0)
{
Arr[j+1] = Arr[j];
--j;
}
Arr[j + 1] = val;
}
}
int main()
{
int Arr[] = {20, 80, 12, 34, 1, 56, 100, 7, 21, 15};
int len = sizeof(Arr) / sizeof(Arr[0]);
Insertion_sort(Arr, len);
printf("The sorted array is: \n");
for (int index = 0; index < len; index++)
printf("%d ", Arr[i]);
printf("\n");
}
```

### Insertion Sort Implementation in C++

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

void Insertion_sort(int Arr[], int n)
{
for (int position = 1; position<n; position++)
{
int val = Arr[position];
int j = position - 1;
while (val < Arr[j] && j >= 0)
{
Arr[j+1] = Arr[j];
--j;
}
Arr[j + 1] = val;
}
}
int main()
{
int Arr[] = {20, 80, 12, 34, 1, 56, 100, 7, 21, 15};
int len = sizeof(Arr) / sizeof(Arr[0]);
Insertion_sort(Arr, len);
cout << "Sorted array:\n";
for (int i = 0; i < len; i++)
{
cout << "The sorted arrayis:  " << Arr[i];
}
cout << "\n";
return 0;
}
```

### Implementation of Insertion Sort in Java

```public class insertionSort
{
void Insertion_sort(int Arr[])
{
int len = Arr.length;
for (int position = 1; position<len; position++)
{
int val = Arr[pos];
int j = position - 1;
while (j >= 0 && val < Arr[j])
{
Arr[j + 1] = Arr[j];
--j;
}
Arr[j + 1] = val;
}
}
public static void main(String args[])
{
int data[] = {20, 80, 12, 34, 1, 56, 100, 7, 21, 15};
insertionSort is = new insertionSort();
is.Insertion_sort(data);
System.out.println("The sorted Array is: ");
for (int i=0;i<data.length; i++)
System.out.print(data[i] + " ");
}
}
```

### Insertion Sort Implementation in Python

```def Insertion_sort(Arr):
for position in range(1, len(Arr)):
value = Arr[position]
j = position - 1

while j >= 0 and value < array[j]:
Arr[j + 1] = Arr[j]
j = j - 1

Arr[j + 1] = value
list = [20, 80, 12, 34, 1, 56, 100, 7, 21, 15]
Insertion_sort(list)
print('The sorted Array is:')
print(list)
```

### Complexity Analysis of Insertion Sort

The time complexity of the insertion sort algorithm is mainly dependent on two operations- the number of comparison operations and the number of swaps.
For insertion sort, the time complexities are:

 Scenario Time complexity Best case O(1) Average case O(n2) Worst case O(n2)

The space complexity for insertion sort is O(1).

### Insertion Sort for Singly Linked List

A singly-linked list is a linear data structure. Hence, just like an array, we can apply insertion sort on the linked list elements as well.

The following steps need to be followed:

1: The first step is to create an empty list, which will always be sorted.

2: Start traversing the list.

3: As we traverse the list, insert the current node each time, in a sorted way into the linked list.

4: Point the head of the given list to that of the sorted linked list.

### Insertion Sort Implementation for Linked List using C++

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

struct Node {
int key;
struct Node* Next;
Node(int x)
{
key = x;
Next = NULL;
}
};

public:
Node* sorted_list;

void Push(int key)
{
Node* New_node = new Node(key);
}
{
sorted_list = NULL;
while (current != NULL) {
Node* Next = current->Next;
Insert_into_sorted(current);
current = Next;
}
}

void Insert_into_sorted(Node* New_node)
{
if (sorted_list == NULL || sorted_list->key >= New_node->key) {
New_node->Next = sorted_list;
sorted_list = New_node;
}
else {
Node* current = sorted_list;
while (current->Next != NULL && current->Next->key < New_node->key) {
current = current->Next;
}
New_node->Next = current->Next;
current->Next = New_node;
}
}
{
cout << Head->key << " ";
}
}
};

int main()
{
list.push(10);
list.push(40);
list.push(8);
list.push(7);
list.push(52);
cout << "Before sorting, the linked list is: " << endl;
cout << endl;
cout << "Linked List After sorting: " << endl;
}
```

### Implementation of Insertion Sort for Linked List using Java:

```public class LinkedList
{
node sorted_list;

class node
{
int key;
node Next;

public node(int key)
{
this.key = key;
}
}

void Push(int key)
{
node New_node = new node(key);
}

{
sorted_list = null;
while (current != null)
{
node Next = current.Next;
Insert_into_sorted(current);
current = Next;
}
}

void Insert_into_sorted(node New_node)
{
if (sorted_list == null || sorted_list.key >= New_node.key)
{
New_node.Next = sorted_list;
sorted_list = New_node;
}
else
{
node current = sorted_list;
while (current.Next != null && current.Next.key < New_node.key)
{
current = current.Next;
}
New_node.Next = current.Next;
current.Next = New_node;
}
}

{
{
}
}

public static void main(String[] args)
{
list.push(10);
list.push(40);
list.push(8);
list.push(7);
list.push(52);
}
}
```

### Insertion Sort Implementation for Linked List using Python:

```class Node:
def __init__(self, key):
self.keya = key
self.Next = None

sorted_list = None
while (current != None):
Next = current.Next
sorted_list = Insert_into_sorted(sorted_list, current)
current = Next

current = None

else:
while (current.Next != None and current.Next.key < New_node.key):
current = current.Next
New_node.Next = current.Next
current.Next = New_node

while(temp != None):
print( temp.key, end = " ")
temp = temp.Next

New_node = Node(0)
New_node.key = New_key

a = None
a = push(a, 10)
a = push(a, 40)
a = push(a, 8)
a = push(a, 7)
a = push(a, 52)

print("Linked List before sorting is: ")
Display_list(a)

a = Insertion_sort(a)

print("\nLinked List after sorting is: ")
Display_list(a)
```

### Applications of Insertion Sort

• Insertion sort is the best algorithm when the number of elements is small i.e. for a small input size.
• Insertion sort is also the best when the data is already sorted. This is because insertion sort takes the least execution time in such a case as compared to other sorting techniques.
• When we don’t have access to all the data initially, we use insertion sort. This is because insertion sort never requires all the elements at a time for sorting. Thus, it is best suitable when the data is arriving one by one.

### Conclusion

Insertion sort in another sorting algorithm useful for small input size. It is best suited when we have online data i.e. the data arriving one by one. It is a stable sorting algorithm with a time complexity of O(n2).

In this article, we have learned the basic idea behind insertion sort. We have also seen the working and the implementation of insertion sort in various programming languages.

TechVidvan Team

The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today’s tech industry.