Summary: In this tutorial, we will learn what 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:
- Loop from
i=1
toi<array.length
- Select array[i] and assign
pos=i
. - Nest another Loop from
j=i-1
toj>=0
- Check
if(array[i] < array [j])
. - If yes then shift array[j] to the right (i.e.
array[j+1]=array[j]
) and assignpos=j
. - If not then assign
pos=j+1
break the nested loop. - End nested
j
loop. - Assign array[i] to index position
pos
(i.e.array[pos]=array[i]
). - End
i
loop.
Here step-2 is selecting the array element and step-3 to step-7 shift all the elements to the right which are greater than the selected element.
Finally, step-8 places the selected element to its correct position.
Here is the implementation of the insertion sort algorithm in C and Java.
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | 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 46In 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.