Binary insertion sort in C: solved sorting exercise

Binary insertion method in C

If you are looking for a binary insertion sort in C solved exercise, this post gives you the full implementation and the key reasoning.

Binary insertion sort is a variation of insertion sort. It uses binary search to find the insertion position, but still shifts elements linearly.

Problem statement

Implement binary insertion sort to sort an integer array in ascending order.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>

int insertion_position(const int a[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (a[mid] <= key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

void binary_insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int pos = insertion_position(a, 0, i - 1, key);

        for (int j = i - 1; j >= pos; j--) {
            a[j + 1] = a[j];
        }
        a[pos] = key;
    }
}

int main(void) {
    int a[] = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54, 54};
    int n = (int)(sizeof(a) / sizeof(a[0]));

    binary_insertion_sort(a, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Expected output

1

0 12 17 23 31 37 46 54 54 72 88 100

Common mistakes

  • Searching in the wrong range (0..i instead of 0..i-1).
  • Forgetting to shift elements before placing key.
  • Using an incorrect repeated-value condition and losing stability.
  • Assuming it becomes O(n log n): shifts are still linear.

Practical use

This exercise helps you:

  • separate comparison cost from movement cost,
  • practice binary search on a sorted prefix,
  • prepare interview questions that ask for insertion-sort optimizations.

Guided practice and next step

If you want a complete path with progressive difficulty:

FAQ

Is binary insertion sort faster than insertion sort in C?

It reduces comparisons with binary search, but still shifts elements, so worst-case time does not become linearithmic.

What is its time complexity?

Average and worst-case time remain O(nĀ²) due to shifts. Position search is O(log n), but does not dominate total runtime.

When is it worth practicing?

When you want to improve insertion-sort intuition and combine searching and sorting in one focused exercise.