Insertion Sort

When we need to sort small number of elements, Insertion sort would be an efficient algorithm. Insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.(Wikipedia)

Worst case performance - O(n^2)

Source - Introduction to Algorithms 3e

C++

void insertion_sort(int array[], int length)
{
    for(int j=1; j<length; j++)
    {
        int key = array[j];
        int i = j-1;
        while(i>=0 && array[i]>key)
        {
            array[i+1] = array[i];
            i = i-1;
        }
        array[i+1] = key;
    }
}

Java

public int[] insertion_sort(int[] array) {
    for (int j = 1; j < array.length; j++) {
        int key = array[j];
        int i = j - 1;
        while (i >= 0 && array[i] > key) {
            array[i + 1] = array[i];
            i = i - 1;
        }
        array[i + 1] = key;
    }
    return array;
}

Matlab

function array = insertion_sort(array)
    for i = 2:numel(array)
        key = array(i);
        j = i - 1;
        while (j > 0) && (array(j) > key)
            array(j+1) = array(j);
            j = j-1;
        end
        array(j+1) = key;
    end
end

Python

def insertion_sort(array):
   for j in range(1,len(array)):

     key = array[j]
     i = j

     while i>0 and array[i-1]>key:
         array[i] = array[i-1]
         i = i-1

     array[i] = key

If we closely look at the Insertion sorting algorithm, we can see that still it is possible to increase the efficiency of the algorithm by doing some changes. Since the correct position of the inserting element is found from the already sorted part of the array, we can perform binary search algorithm to that part of the array. Here is the Python implementation of the modified algorithm.

def insertion_sort(array):
    for i in range(1, len(array)):
 
        key = array[i]
        low, high = 0, i
     
        while high > low:
            mid = (low + high) // 2
            if array[mid] < key:
                low = mid + 1           
            else:
                high = mid
             
     array[:] = array[:low] + [key] + array[low:i] + array[i+1:]