Insertion Sort

Sorting Algorithm


About Insertion Sort

In this technique we pick an element and then insert it at the appropriate position in ascending or descending order.
In pass 1, element a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted.
In pass 2, a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that a[0], a[1] and a[2] are sorted.
In a similar way the process is carried out n-1 times.

  • Insertion sort requires n – 1 pass to sort an array of n elements.
  • In each pass we insert the current element at the appropriate place so that the elements in the current range is in order.
  • In each pass we have k comparisons, where k is the pass number.
    So, 1st pass requires 1 comparison,
    kth pass requires k – 1 comparisons and
    the last pass requires n – 1 comparisons


a[0:n-1] is an array of n elements.
temp is a variable to facilitate exchange.
    for k = 1 to n-1 by 1 do	//this is for pass
        Set temp = a[k];
        Set j = k-1;
        while( temp < a[j] and j >= 0) do
            Set a[j+1] = a[j];
            Set j = j-1;
        Set a[j+1] = temp;

Code in C

Code in C

#include <stdio.h>

//function declaration
void insertionSort(int *a, int n);

int main(){
	//variable declaration
	int arr[5], i;
	for(i = 0; i < 5; i++)
		scanf("%d", &arr[i]);
	insertionSort(arr, 5);	//passing arr address and no. of elements
	for(i = 0; i < 5; i++)
		printf("%d\n", arr[i]);
	return 0;

//function definition
void insertionSort(int *a, int n){
	int k, j, temp;
	for(k = 1; k <= n-1; k++){
		temp = a[k];
		j = k-1;
		while(temp < a[j] && j >= 0){
			a[j+1] = a[j];
		a[j+1] = temp;

Time Complexity

1st pass requires 1 comparison
2nd pass required 2 comparison
... last pass requires (n-1) comparison
So, total comparison = 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n2)