Summary: In this tutorial, we will learn what the Insertion sort algorithm is and how to implement the Insertion sort algorithm to sort an array in C and Java.

## Introduction to Insertion sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Wikipedia

Insertion sort is a stable sorting algorithm that is used to sort linear data structures such as array and list.

The algorithm sorts array elements one by one. On each iteration, the sorted partition of the array grows and the unsorted partition shrinks.

The black blocks represent the sorted partition and otherwise represent the unsorted partition of the array.

In the above example, the Insertion sort algorithm picks one element (red block) at a time and place it to its correct position in the sorted partition.

The algorithm repeats this process for every element and in the end, the array is sorted.

## Insertion Sort Algorithm

Steps to implement Insertion Sort Algorithm:

1. Loop from `i=1` to `i<array.length`
2. Select `array[i]` and assign `pos=i`.
3. Nest another Loop from `j=i-1` to `j>=0`
1. Check `if(array[i] < array [j])`.
2. If yes then shift `array[j]` to the right (i.e. `array[j+1]=array[j]` and assign `pos=j`)
3. If not then assign `pos=j+1` break the nested loop.
4. End nested `j` loop.
5. Assign `array[i]` to index position `pos` (i.e. `array[pos]=array[i]`).
6. End `i` loop.

Here we select the array element in step-2 and shift all the elements greater than it to the right from step-3 to step-7.

Finally, in step-8, we place the selected element in its correct position.

Here is the implementation of the insertion sort algorithm in C, Java, and Python.

## Python

``````def insertionSort(arr):

for i in range(1, len(arr)):
element = arr[i]
pos = i
for j in range(i-1, -1, -1):
if arr[j] > element:
arr[j+1] = arr[j]
pos = j
else:
break
arr[pos] = element

return arr

if __name__ == '__main__':
arr = [8, 36, -51, 9, 21, 46, 2]
print(arr)

insertionSort(arr)
print(arr)``````

## C

``````#include <stdio.h>
#include <stdlib.h>
void insertSort(int[], int);
void display(int[], int);

int main()
{
int a[] = {8, 36, -51, 9, 21, 46, 2};

printf("Unsorted array \n");
display(a,7);

insertSort(a, 7);

printf("Sorted array \n");
display(a,7);

return 0;
}

void display(int a[], int size){
for(int i=0; i< size; i++){
printf("%d ", a[i]);
}
printf("\n");
}

void insertSort(int a[], int size){
int temp, i, j, pos;
for(i=1; i<size; i++){
//Pick element

temp = a[i];
pos = i;

//Place temp in the sorted partition
for(j=i-1; j>=0; j--){
if(temp < a[j]){
a[j+1] = a[j];
pos = j;
} else {
pos = j+1;
break;
}
}
a[pos] = temp;
}
}``````

## Java

``````public class InsertionSort {
int a[];

public InsertionSort(int[] a) {
this.a = a;
}

public void sort(int a[]){
int temp, i, j, pos;
for(i=1; i<a.length; i++){
//Pick element
temp = a[i];
pos = i;

//Place temp in the sorted partition
for(j=i-1; j>=0; j--){
if(temp < a[j]){
a[j+1] = a[j];
pos = j;
} else {
pos = j+1;
break;
}
}
a[pos] = temp;
}
}
}

public class App {
public static void main(String args[]){
int a[] = {8, 36, -51, 9, 21, 46, 2};
InsertionSort is = new InsertionSort(a);

System.out.println("Unsorted array ");
display(a);

is.sort(a);

System.out.println("Sorted array ");
display(a);
}

private static void display(int[] a) {
for(int i=0; i< a.length; i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
}``````

Output

Unsorted array
8 36 -51 9 21 46 2
Sorted array
-51 2 8 9 21 36 46

In the above program, the `temp` variable stores the copy of the selected element because on right swapping the greater elements its value gets overwritten in the array.

The `pos` variable, stores the correct position of the selected array element.

### Insertion Sort Overview

• In-place algorithm – No extra array is needed.
• O(n²) time complexity – quadratic.
• Stable algorithm – Doesn’t interchange the same values in the array.
• Quite Efficient for data sets that are already substantially sorted.

In this tutorial, we learned what Insertion sort algorithm is and how to implement Insertion sort algorithm to sort an array in C and Java programming languages.