• Home
• Contact

Description

Element number n gets inserted at the proper position and all already inserted (indices 0..n-1) elements get moved one position.

• stable
• for ‘almost sorted’ arrays is insertion sort linear
• best case: $O(n)$, other cases: $O(n^2)$

Algorithm

for (int i = 1; i < array.count(); ++i) {
    int j = i;
    while (j > 0) {
        if (array[j-1] > array[j]) {
            array.swap( j-1, j );
        }
        --j;
    }
}

Analysis

$M_{min} = 0$

$M_{max} = (n^2 - n) / 2$

$M_{avg} = (n^2 - n) / 4$

⇒ $O(n^2)$

$C_{min} = n - 1$

$C_{max} = (n^2 - n) / 2$

$C_{avg} = (n^2 + 3n - 4) / 4$

⇒ $O(n^2)$