QUESTION 27 · Sorting

How does insertion sort extend its sorted prefix?

2 marks

Answer

It takes the next key, shifts larger preceding values right and inserts the key into the gap.

The prefix begins with the first element.
Using a strict greater-than shift keeps equal values in their original order.

Explain insertion sort and write a C program for ascending order.

5 marks

Answer in brief

Insertion sort builds a sorted prefix by inserting each next value into its correct position among the values already processed.

Algorithm

Treat the first element as a sorted prefix.
Save the next value as key.
Move preceding values one position right while they are larger than key.
Store key in the remaining gap and continue with the next element.

Worked trace

For 5, 1 and 4, key 1 is saved first. Since 5 is larger, shift it right and insert 1 at index 0, giving 1, 5, 4. Next save key 4. Shift 5 right, stop at 1 and insert 4 between them. The result is 1, 4, 5.

Why save the key?

Shifting overwrites array positions. Saving the selected value in a separate variable prevents it from being lost before the gap is ready. The condition j >= 0 && a[j] > key checks the boundary first, so short-circuit evaluation avoids reading a[-1].

Time complexity

For already sorted input, each key needs only a small comparison and no shifting, giving O(n) best-case time. For reverse order, the shifts total 1 + 2 + ... + (n - 1), giving O(n²) worst-case time. The usual average case is quadratic too. It can be useful for small or nearly sorted arrays.

Space and stability

Only a key and counters are added, giving O(1) auxiliary space. Shifting only strictly larger values keeps equal values in their prior relative order, so this version is stable.

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j]; --j;
        }
        a[j + 1] = key;
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

Sample input and output

Input

3
5 1 4

Output

1 4 5