Insertion Sort


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.

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: ΘO(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.

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).