Given an array of integers, sort it using insertion sort algorithm.
Insertion sort is stable, in-place sorting algorithm that builds the final sorted array one item at a time. It is not very best in terms of performance but it is more efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort. Insertion sort is also used is used in Hybrid sort which combines different sorting algorithms to improve performance.
It is also a well known online algorithm as it can sort a list as it receives it. In all other algorithms we need all elements to be provided to the sorting algorithm before applying it. But an insertion sort allows we to start with partial set of elements, sorts it (called as partially sorted set), and if we want, we can insert more elements (these are the new set of elements that were not in memory when the sorting started) and sorts these elements too. In real world, data to be sorted is usually not static, rather dynamic. If even one additional element is inserted during the sort process, other algorithms don’t respond easily. But only this algorithm is not interrupted and can respond well with the additional element.
How it works?
The idea is to divide the array into two subsets – sorted subset and unsorted subset. Initally sorted subset consists of only one first element at index 0. Then for each iteration, insertion sort removes next element from the unsorted subset, finds the location it belongs within the sorted subset, and inserts it there. It repeats until no input elements remain. Below example explains it all –
i = 1 [ 3 8 5 4 1 9 -2 ]
i = 2 [ 3 8 5 4 1 9 -2 ]
i = 3 [ 3 5 8 4 1 9 -2 ]
i = 4 [ 3 4 5 8 1 9 -2 ]
i = 5 [ 1 3 4 5 8 9 -2 ]
i = 6 [ 1 3 4 5 8 9 -2 ]
[ -2 1 3 4 5 8 9 ]
Iterative C and Java implementation –
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 |
#include <stdio.h> // perform insertion sort on arr[] void insertionSort(int arr[], int n) { // Start from second element (element at index 0 // is already sorted) for (int i = 1; i < n; i++) { int value = arr[i]; int j = i; // Find the index j within the sorted subset arr[0..i-1] // where element arr[i] belongs while (j > 0 && arr[j - 1] > value) { arr[j] = arr[j - 1]; j--; } // Note that subarray arr[j..i-1] is shifted to // the right by one position i.e. arr[j+1..i] arr[j] = value; } } // Function to print n elements of the array arr void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); } int main(void) { int arr[] = { 3, 8, 5, 4, 1, 9, -2 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); // print the sorted array printArray(arr, n); return 0; } |
Output:
-2 1 3 4 5 8 9
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 |
import java.util.Arrays; class InsertionSort { // Function to perform insertion sort on arr[] public static void insertionSort(int[] arr) { // Start from the second element // (element at index 0 is already sorted) for (int i = 1; i < arr.length; i++) { int value = arr[i]; int j = i; // Find the index j within the sorted subset arr[0..i-1] // where element arr[i] belongs while (j > 0 && arr[j - 1] > value) { arr[j] = arr[j - 1]; j--; } // Note that sub-array arr[j..i-1] is shifted to // the right by one position i.e. arr[j+1..i] arr[j] = value; } } public static void main(String[] args) { int[] arr = { 3, 8, 5, 4, 1, 9, -2 }; insertionSort(arr); // print the sorted array System.out.println(Arrays.toString(arr)); } } |
Output:
[-2, 1, 3, 4, 5, 8, 9]
Recursive C and Java implementation –
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 |
#include <stdio.h> // recursive function to perform insertion sort on subarray arr[i..n] void insertionSort(int arr[], int i, int n) { int value = arr[i]; int j = i; // Find index j within the sorted subset arr[0..i-1] // where element arr[i] belongs while (j > 0 && arr[j - 1] > value) { arr[j] = arr[j - 1]; j--; } arr[j] = value; // Note that subarray arr[j..i-1] is shifted to // the right by one position i.e. arr[j+1..i] if (i + 1 <= n) { insertionSort(arr, i + 1, n); } } // Function to print n elements of the array arr void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); } int main(void) { int arr[] = { 3, 8, 5, 4, 1, 9, -2 }; int n = sizeof(arr) / sizeof(arr[0]); // Start from second element (element at index 0 // is already sorted) insertionSort(arr, 1, n - 1); // print the sorted array printArray(arr, n); return 0; } |
Output:
-2 1 3 4 5 8 9
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 |
import java.util.Arrays; class InsertionSort { // Recursive function to perform insertion sort on sub-array arr[i..n] public static void insertionSort(int[] arr, int i, int n) { int value = arr[i]; int j = i; // Find index j within the sorted subset arr[0..i-1] // where element arr[i] belongs while (j > 0 && arr[j - 1] > value) { arr[j] = arr[j - 1]; j--; } arr[j] = value; // Note that subarray arr[j..i-1] is shifted to // the right by one position i.e. arr[j+1..i] if (i + 1 <= n) { insertionSort(arr, i + 1, n); } } public static void main(String[] args) { int[] arr = { 3, 8, 5, 4, 1, 9, -2 }; // Start from second element (element at index 0 // is already sorted) insertionSort(arr, 1, arr.length - 1); // print the sorted array System.out.println(Arrays.toString(arr)); } } |
Output:
[-2, 1, 3, 4, 5, 8, 9]
The worst case time complexity of insertion sort is O(n2). The worst case happens when the array is reverse sorted. The best case time complexity of insertion sort is O(n). The best case happens when the array is already sorted.
The auxiliary space used is O(1) by the iterative version and O(n) by the recursive version for the call stack.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Very well described.. Your explanation made it so easy for me to understand this concept of Insertion sort.
In the recursive implementation, the last if condition statement should be ‘(i+1)<n' and not 'i+1<=n'. Because if not then the last recursive call would assign value = a[n], which will give error.
Thanks for sharing your concerns.. If you take another look, we’re passing n-1 index (not n) to insertion sort function, so that should work fine.
insertionSort(arr, 1, n - 1);
Please let us know if you have any other concerns. Happy coding 🙂