Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element at a time and inserting it into its correct position in the sorted array.

Features

• Stable sorting algorithm
• In-place sorting algorithm

Pseudocode

procedure insertionSort(A : list of sortable items)
    for i = 1 to length(A) - 1 do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j + 1] = A[j]
            j = j - 1
        end while
        A[j + 1] = key
    end for
end procedure

Java

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Runtime Analysis

Given $N$ elements in the array and $K$ inversion pairs, the time complexity of insertion sort is $\Theta (N+K)$.

Best Case

The best case occurs when the array is already sorted. In this case, the algorithm makes a single pass through the array and does not perform any swaps. The time complexity is $\Omega (N)$.

Worst Case

The worst case occurs when the array is sorted in reverse order. In this case, the algorithm makes $N-1$ passes through the array, performing $N-1$ swaps on the first pass, $N-2$ swaps on the second pass, and so on. The total number of inversion pairs, $K$ in a reverse-sorted array, is given by:

This results in a time complexity of $O(N^2)$.

Source

The existing course note was retained and normalized during the merge.

Related: Topic index.