Insertion Sort
Get this book > Problems on Array: For Interviews and Competitive Programming
Insertion sort is an online stable inplace sorting algorithm that builds the final sorted list one item at a time. It works on the principle of moving a element to its correct position in a sorted array.
Advantages of Insertion Sort:
 Stable: it does not change the relative order of elements with equal keys
 Inplace: it only requires a constant amount O(1) of additional memory space
 Online: it can sort a list as it receives it
 Simple implementation: Jon Bentley shows a threeline C version, and a fiveline optimized version
 Efficient for small data sets, much like other quadratic sorting algorithms
 More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
 Adaptive: efficient for data sets that are already substantially sorted
Complexity
 Worst case time complexity:
Θ(N^2)
comparisons and swaps  Average case time complexity:
Θ(N^2)
comparisons and swaps  Best case time complexity:
Θ(N)
comparisons andΘ(1)
swaps  Space complexity:
Θ(1)
.
Explanation
In Insertion sort, the list is divided into two parts: the sorted part followed by the unsorted part.
In each step, pick the first element from the unsorted part and insert in the correct position in the sorted part.
Initially, the sorted part is empty and finally, the unsorted part is empty.
Pseudocode
Following is the pseudocode of Insertion Sort for a zero indexed array:
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j1] > A[j]
swap A[j] and A[j1]
j ← j  1
end while
i ← i + 1
end while
Implementations
Implementation of Insertion Sort algorithm in 5 languages that includes C
, C++
, Java
, Python
and Haskell
.
 C
 C++
 Java
 Python
 Haskell
C
#include <stdio.h>
// Part of Cosmos by OpenGenus Foundation
void insertion(int*, int);
int main()
{
int n;
scanf("%d", &n);
int arr[n];
for(int i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
insertion(arr, n);
return 0;
}
void insertion(int arr[], int n)
{
int key;
int j;
for(int i=1;i<n;i++)
{
key = arr[i];
j = i1;
while(j>=0 && arr[j]>key)
{
arr[j+1] = arr[j];
j;
}
arr[j+1] = key;
}
for(int i=0;i<n;i++)
{
printf("%d\t", arr[i]);
}
printf("\n");
}
C++
/*
Part of Cosmos by OpenGenus Foundation
insertion sort synopsis
template<typename _Bidirectional_Iter, typename _Compare>
void
insertionSort(_Bidirectional_Iter begin, _Bidirectional_Iter end, _Compare compare);
template<typename _Bidirectional_Iter>
void
insertionSort(_Bidirectional_Iter begin, _Bidirectional_Iter end);
*/
#include <functional>
template<typename _Bidirectional_Iter, typename _Compare>
void
insertionSort(_Bidirectional_Iter begin, _Bidirectional_Iter end, _Compare compare)
{
if (begin != end)
{
auto backOfBegin = begin;
backOfBegin;
auto curr = begin;
for (++curr; curr != end; ++curr)
{
auto pivot = *curr;
auto backward = curr;
auto nextOfBackward = curr;
while (backward != backOfBegin && compare(pivot, *backward))
{
*nextOfBackward = *backward;
nextOfBackward;
}
*nextOfBackward = pivot;
}
}
}
template<typename _Bidirectional_Iter>
void
insertionSort(_Bidirectional_Iter begin, _Bidirectional_Iter end)
{
using value_type = typename std::iterator_traits<_Bidirectional_Iter>::value_type;
insertionSort(begin, end, std::less<value_type>());
}
Java
// Part of Cosmos by OpenGenus Foundation
class InsertionSort {
void sort(int arr[]) {
for (int i = 0; i < arr.length; ++i) {
for (int j = i; j > 0 && arr[j  1] > arr[j]; j) {
int temp = arr[j];
arr[j] = arr[j  1];
arr[j  1] = temp;
}
}
}
// Driver method
public static void main(String args[]) {
int arr[] = {8, 2, 111, 3, 15, 61, 17};
System.out.println("Before: " + Arrays.toString(arr));
InsertionSort ob = new InsertionSort();
ob.sort(arr);
System.out.println("After:" + Arrays.toString(arr));
}
}
Python
'''
Part of Cosmos by OpenGenus Foundation
Program for InsertionSort sorting
'''
def insertion_sort(L):
length = len(L)
for i in range(length):
key = L[i]
j = i  1
while j >= 0 and key < L[j]:
L[j + 1] = L[j]
j = 1
L[j + 1] = key
return L
if __name__ == "__main__":
#creating a random array of length 100
L = np.random.random_integers(100, size=(100, )).tolist()
print("Given array : \n", L)
print("Sorted array : \n", insertion_sort(L))
Haskell
{
Part of Cosmos by OpenGenus Foundation
}
insertion_sort :: Ord a => [a] > [a]
insertion_sort [] = []
insertion_sort [x] = [x]
insertion_sort (x:arrx) = insert $ insertion_sort arrx
where insert [] = [x]
insert (y:arry)
 x < y = x : y : arry
 otherwise = y : insert arry
main = do
let arr = [3,5,12,56,92,123,156,190,201,222]
putStrLn("Sorted Array: "
++ show(insertion_sort(arr)))
Applications
Applications of Insertion Sort are as follows:

If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction, then using binary insertion sort may yield better performance.

A variant named binary merge sort uses a binary insertion sort to sort groups of 32 elements, followed by a final sort using merge sort.

If a skip list is used, the insertion time is brought down to O(log n), and swaps are not needed because the skip list is implemented on a linked list structure. The final running time for insertion would be O(n log n).