A Deep Dive Into Insertion Sort - Analysis and Implementation

Insertion Sort

Pseudocode

Analysis

• Best case: The list is already sorted, resulting in $(n - 1)$ comparisons.
• Worst case: The list is in reverse order; each iteration shifts the element all the way to the beginning of the sorted portion.
• Comparison count in worst case: The first iteration makes 1 comparison, the second at most 2, and so on, up to the last iteration making at most $(n - 1)$ comparisons. This sums up to:
  $$ \sum_{i=1}^{n-1}i=\frac{n(n-1)}{2} $$
• Worst-case time complexity: $O(n^2)$
• Average-case time complexity: A more complex analysis yields $O(n^2)$, similar to the worst case.
• Practical consideration: Insertion sort is inherently adaptive, meaning its performance improves if the input list is already partially sorted. This characteristic ensures good performance in practice for specific scenarios.
• Efficiency: Very efficient on small lists, especially if they possess some existing structure (partially ordered).

Code Samples

Code Sample 13: Java Insertion Sort for integers

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

Code Sample 14: C Insertion Sort for integers

void insertionSort(int *array, int size) {
    int value;
    for (int i = 1; i < size; i++) {
        value = array[i];
        int j = i;
        while (j > 0 && array[j - 1] > value) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = value;
    }
}