## What is Insertion Sort Algorithm?

• It is one of the easiest and brute force sorting algorithm
• Insertion sort is used to sort elements in either ascending or descending order
• In insertion sort, we maintain a sorted part and unsorted part
• It works just like playing cards i.e, picking one card and sorting it with the cards that we have in our hand already
• With every iteration, one item is moved from the unsorted section to the sorted section
• The first element is picked and is considered sorted
• After this, we start picking from the second element onward and compare with elements in the sorted section
• We keep shifting the elements from the sorted section one by one until an appropriate location is found for that element
• This process is continued until all elements have been exhausted

## Insertion Sort Algorithm Pseudo-code

• Take the first element and consider it to be a sorted part(a single element is always sorted)
• Now pick arr[1] and store it is a temporary variable
• Start comparing the values of tmp with elements of the sorted part from the rear side
• If tmp is less than the rear element, say arr[k], then shift arr[k] to k+1 index
• This shifting will continue until the appropriate location is identified. Then, we will put the temporary element at the identified location
• This will continue for all the elements, and we will have our desired sorted array in ascending order

## Insertion Sort Algorithm

Insertion Sort(arr, size)
consider 0th element as sorted part
for each element from i=2 to n-1
tmp = arr[i]
for j=i-1 to 0
If a[j]>tmp
Then right shift it by one position
put tmp at current j

## Insertion Sort Dry Run

Input:

First step- marking of the sorted part

After i=1

After i=2

After i=3

After i=4

## Insertion Sort Time Complexity

• In the worst-case scenario, n will pick all elements and then n shifts to set it to the right position
• In the best-case scenario, that is a sorted array, we will just pick the elements, but no shifting will take place leading it to n time complexity, that is, every element is traversed at least once
• Best Time Complexity: O(n)
• Average Time Complexity: O(n^2)
• Worst Time Complexity: O(n^2)

## Insertion Sort Space Complexity

• No auxiliary space is required in insertion sort implementation. That is, we are not using any arrays, linked list, stack, queue, etc, to store our elements
• Hence space complexity is: O(1)

Also Read: Facial Recognition using Python

## Insertion Sort Algorithm in C

#include <stdio.h>
// function to print the elements of the array
void display(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// function to sort the elements of the array
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int tmp = arr[i];
int j = i - 1;

while (tmp < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = tmp;
}
}
// main function or driver function
int main() {
int arr[] = {9, 5, 1, 4, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Elements before sorting:\n");
display(arr, n);
insertionSort(arr, n);
printf("Elements after sorting:\n");
display(arr, n);
}

Output of the program:
Elements before sorting:
9 5 1 4 3
Elements after sorting:
1 3 4 5 9

## Insertion Sort in Java

import java.util.*;

class InsertionSort {

//method for sorting the elements
void insertionSort(int arr[]) {
int size = arr.length;

for (int i = 1; i < size; i++) {
int tmp = arr[i];
int j = i - 1;

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

arr[j + 1] = tmp;
}
}

// method for printing the elements
void display(int arr[]) {
int size = arr.length;
for (int i = 0; i < size; i++)
System.out.print(arr[i]+" ");
System.out.println();

}
// Main method or driver method
public static void main(String args[]) {
int[] arr = { 9, 5, 1, 4, 3 };
InsertionSort  ob = new InsertionSort();
System.out.println("Elements before sorting: ");
ob.display(arr);
ob.insertionSort(arr);
System.out.println("Elements after sorting: ");
ob.display(arr);
}
}

Output of the program:
Elements before sorting:
9 5 1 4 3
Elements after sorting:
1 3 4 5 9

## Insertion Sort in C++

#include <iostream>
using namespace std;

//Function for displaying the elements
void display(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

// Function for sorting the elements
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int tmp = arr[i];
int j = i - 1;
while (tmp < arr[j] && j >= 0) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = tmp;
}
}

// Main Function or Driver Function
int main() {
int data[] = {9, 5, 1, 4, 3};
int size = sizeof(data) / sizeof(data[0]);
cout << “Elements before sorting:\n";
display(data, size);
insertionSort(data, size);
cout << "Elements after sorting:\n";
display(data, size);
}

Output of the program:
Elements before sorting:
9 5 1 4 3
Elements after sorting:
1 3 4 5 9

## Insertion Sort in Python

// Code for sorting the elements
def insertionSort(arr):

for i in range(1, len(arr)):
tmp = arr[i]
j = i - 1

while j >= 0 and tmp < arr[j]:
arr[j + 1] = arr[j]
j = j - 1

arr[j + 1] = tmp

// Main code or Driver Code
arr = [9, 5, 1, 4, 3]
print('Elements before sorting:')
print(arr)
insertionSort(arr)
print('Elements after sorting:')
print(arr)

Output of the program:
Elements before sorting:
[ 9, 5, 1, 4, 3]
Elements after sorting:
[1, 3, 4, 5, 9]

Also Read: Python Tutorial for beginners

## Insertion Sort Example

#### Example1:

Given the linked list with unsorted data in it, we need to sort the data.

Example:

Input: -1->5->3->4->0

Output: -1->0->3->4->5

Code: JAVA

public class List {
node sorted;

//Structure of the node that is the data part and the next part which points the next node
class node {
int data;
node next;

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

void insert(int data) {
node newnode = new node(data);
}

sorted = null;

while (curr != null) {
node next = curr.next;
sortedInsert(curr);
curr = next;
}
}

void sortedInsert(node newnode) {
if (sorted == null || sorted.data >= newnode.data) {
newnode.next = sorted;
sorted = newnode;
} else {
node curr = sorted;
while (curr.next != null && curr.next.data < newnode.data) {
curr = curr.next;
}
newnode.next = curr.next;
curr.next = newnode;
}
}

}
System.out.println();
}

public static void main(String[] args) {
List list = new List();
list.insert(5);
list.insert(20);
list.insert(4);
list.insert(3);
list.insert(30);
System.out.println("Original list:");
System.out.println("Sorted list:");
}
}

Output of the program:

Original list:
5 20 4 3 30

Sorted list:
3 4 5 20 30

Code: C

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node* next;
};

void sortedInsert(struct Node**, struct Node*);

{
struct Node *sorted = NULL;

while (curr != NULL)
{
struct Node *next = curr->next;

sortedInsert(&sorted, curr);

curr = next;
}

}

void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* curr;
{
}
else
{
while (curr->next!=NULL &&
curr->next->data < new_node->data)
{
curr = curr->next;
}
new_node->next = curr->next;
curr->next = new_node;
}
}

{
while(tmp != NULL)
{
printf("%d ", tmp->data);
tmp = tmp->next;
}
}

void insert(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;

new_node->data = new_data;

}

int main()
{
struct Node *a = NULL;
insert(&a, 5);
insert(&a, 20);
insert(&a, 4);
insert(&a, 3);
insert(&a, 30);

printf("\nOriginal list:\n");
display(a);

insertionSort(&a);

printf("\nSorted list:\n");
display(a);

return 0;
}
Output of the program:

Original list:
5 20 4 3 30

Sorted list:
3 4 5 20 30

#### Example 2:

Given the array, which is a nearly sorted (or K sorted) array, we need to sort the elements in the array.

Example:

Input : {6, 5, 3, 2, 8, 10, 9}

k = 3

Output : {2, 3, 5, 6, 8, 9, 10}

Code: JAVA

class Main{
static void insertionSort(int A[], int size)
{
int i, k, j;
for (i = 1; i < size; i++)
{
k = A[i];
j = i-1;

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

public static void main (String[] args) {
int a[]={2,7,5,9,3,1};
insertionSort(a,6);

}
}

Code: C

void insertionSort(int A[], int size)
{
int i, k, j;
for (i = 1; i < size; i++)
{
k = A[i];
j = i-1;

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

## Difference between Selection, Bubble and Insertion sort

#### 1. In terms of algorithm

In Insertion sort, adjacent elements are compared and sorted if they are in wrong order. We select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and single element is already sorted. We will have array sorted by 1 element in every iteration.

Here, we create partitions of sorted and unsorted parts. One by one element from the sorted part is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.

#### 2. In terms of time and space complexity

All 3 sort have O(n2) time complexity. But via flag variable, we can reduce the time complexity of Insertion and insertion to O(n) is best case. Space Complexity is the same for all i.e., O(1).

#### 3. In terms of speed

Insertion sort may work best with an already sorted array and there is no need for any extra flag.

#### 4. In terms of in-place

In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space. Selection and Insertion are in-place algorithms and do not require any auxiliary memory.

#### 5. In terms of stability

Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same. Insertion and Insertion are stable algorithms but naive selection is not as swapping may cost stability.

We hope you enjoyed this tutorial on Insertion Sort Algorithm. If you wish to upskill, join Great Learning’s free Python course today!

0
Faizan has been working as an Instructor of Data Structure and Algorithm for the last 1 year. He has expertise in languages such as Java, JavaScript, etc. He is a Subject Matter Expert in the field of Computer Science and a Competitive programmer. He has been working in technical content development and is a Research Analyst.