Insertion Sort

Insertion Sort

Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes an element from the input data and inserts it into the correct position in the list being sorted. The choice of the element being removed from the input is random and this process is repeated until all input elements have gone through.

Advantages

• Simple implementation
• Efficient for small data
• Adaptive: If the input list is presorted [may not be completely] then insertions sort takes O(n + d), where d is the number of inversions
• Practically more efficient than selection and bubble sorts, even though all of them have O(n^2) worst case complexity
• Stable: Maintains relative order of input data if the keys are same
• In-place: It requires only a constant amount O(1) of additional memory space
• Online: Insertion sort can sort the list as it receives it

Algorithm

Every repetition of insertion sort removes an element from the input data, and inserts it into the correct position in the already-sorted list until no input elements remain. Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted.

Implementation

void InsertionSort(int A[], int n)
{
    int i, j, e;

    for(i = 1; i <= n - 1; i++)
    {
        e = A[i];
        j = i;

        while(A[j-1] > e && j >= 1)
        {
            A[j] = A[j-1];
            j--;
        }

        A[j] = e;
    }
}

Performance

If every element is greater than or equal to every element to its left, the running time of insertion sort is Θ(n). This situation occurs if the array starts out already sorted, and so an already-sorted array is the best case for insertion sort.

• Worst case complexity: Θ(n^2)
• Best case complexity: Θ(n)
• Average case complexity: Θ(n^2)
• Worst case space complexity: O(n^2) total, O(1) auxiliary.