Insertion Sort Algorithm OpenGenus IQ

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Insertion sort is an online stable in-place 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
In-place: 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 three-line C version, and a five-line 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[j-1] > A[j]
        swap A[j] and A[j-1]
        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 = i-1;
		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).