Binary Sort (Binary Insertion Sort)

Binary Insertion Sort (often simply called "Binary Sort") is a variation of Insertion Sort. In plain Insertion Sort, we find the correct position for the key element by comparing it one by one with elements in the sorted part of the array (a linear search). 

Binary Insertion Sort improves this by using Binary Search to find the correct insertion position, since the left part of the array is already sorted at every step.

This reduces the number of comparisons needed to find the insertion point, although the actual shifting of elements still has to happen one by one, just like normal Insertion Sort.

How Binary Sort Works?

1. Start from the second element (index 1) of the array.
2. Treat the portion of the array before the current element as already sorted.
3. Use Binary Search on this sorted portion to find the correct position where the current element (key) should be inserted.
4. Shift all elements after that position one step to the right to make room.
5. Insert the key at the found position.
6. Repeat for all elements in the array.

Example: Sorting [37, 23, 14, 45, 9]

Initial array: [37, 23, 14, 45, 9]

Pass 1 (i = 1), key = 23

• Sorted portion: [37]
• Binary Search for correct position of 23 in [37] → 23 < 37, so position = 0
• Shift 37 right, insert 23 at index 0
• Array: [23, 37, 14, 45, 9]

Pass 2 (i = 2), key = 14

• Sorted portion: [23, 37]
• Binary Search: compare with middle element 23 → 14 < 23, search left half → position = 0
• Shift 23 and 37 right, insert 14 at index 0
• Array: [14, 23, 37, 45, 9]

Pass 3 (i = 3), key = 45

• Sorted portion: [14, 23, 37]
• Binary Search: compare with middle element 23 → 45 > 23, search right half; compare with 37 → 45 > 37 → position = 3
• No shifting needed (45 already belongs at index 3)
• Array: [14, 23, 37, 45, 9]

Pass 4 (i = 4), key = 9

• Sorted portion: [14, 23, 37, 45]
• Binary Search: compare with middle element (23) → 9 < 23, search left half; compare with 14 → 9 < 14 → position = 0
• Shift all four elements right, insert 9 at index 0
• Array: [9, 14, 23, 37, 45]

Final Sorted Array: [9, 14, 23, 37, 45]

Pseudocode of Binary Sort

Step 1: Start
Step 2: For i = 1 to n-1, repeat steps 3 to 6
Step 3:     key = array[i]
Step 4:     pos = binarySearch(array, 0, i-1, key)   // finds correct insertion index
Step 5:     Shift all elements from pos to i-1 one position to the right
Step 6:     array[pos] = key
Step 7: End

Function binarySearch(array, low, high, key):
    While low <= high:
        mid = (low + high) / 2
        If array[mid] <= key:
            low = mid + 1
        Else:
            high = mid - 1
    Return low

Advantages

• Reduces the number of comparisons to O(log n) per insertion, compared to O(n) in plain Insertion Sort.
• Still stable equal elements maintain their relative order (if binary search is implemented to insert after equal elements).
• Useful when comparison operations are expensive (e.g., comparing long strings or complex objects), since it minimizes comparisons.
• In-place algorithm, requiring no extra array.

Disadvantages

• The number of shift/move operations remains the same as plain Insertion Sort O(n²) in the worst case so overall time complexity does not improve for large datasets.
• Slightly more complex to implement than plain Insertion Sort due to the binary search logic.
• Not beneficial when comparisons are cheap (e.g., comparing simple integers), since the shifting cost dominates anyway.

Time and Space Complexity

Space Complexity: O(1) in-place, aside from recursion space if binary search is implemented recursively (O(log n) in that case).

Stability: Stable In-place: Yes

When to Use Binary Sort?

• When the cost of comparing two elements is significantly higher than the cost of shifting/moving them (e.g., comparing large strings, objects with complex comparison logic).
• Small to medium datasets where reducing comparisons offers a measurable practical benefit.
• Situations where stability is required alongside reduced comparison count.

C Program of Binary Sort

#include <stdio.h>

void binaryInsertionSort(int arr[], int n) {
    int i, j, key, left, right, mid;

    for (i = 1; i < n; i++) {
        key = arr[i];
        left = 0;
        right = i - 1;

        // Binary search to find the correct position
        while (left <= right) {
            mid = (left + right) / 2;

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

        // Shift elements to make space
        for (j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        arr[left] = key;
    }
}

int main() {
    int n, i;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];

    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    binaryInsertionSort(arr, n);

    printf("Sorted array:\n");
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Practice Questions

1. Sort the array [55, 20, 44, 12, 33] using Binary Insertion Sort, showing the binary search steps for each pass.
2. Explain why Binary Insertion Sort reduces the number of comparisons but not the number of shifts, using an example array of 6 elements.
3. For the array [10, 20, 30, 40, 5], trace the binary search used to find the insertion position for the key 5.
4. Compare the total number of comparisons made by plain Insertion Sort versus Binary Insertion Sort for the array [8, 7, 6, 5, 4, 3, 2, 1].
5. Under what circumstances does Binary Insertion Sort provide little to no practical benefit over plain Insertion Sort? Explain with reasoning.
6. Modify the binary search function used in Binary Insertion Sort so that it inserts new elements before equal elements instead of after, and explain how this affects stability.
7. Trace Binary Insertion Sort for the array [3, 1, 4, 1, 5, 9, 2, 6] and list the position found for each key.
8. Write a program implementing Binary Insertion Sort and count separately the number of comparisons and the number of shifts performed.
9. Explain how Binary Insertion Sort could be beneficial when sorting an array of long text strings rather than integers.
10. Given the array [95, 15, 45, 75, 25], manually sort it using Binary Insertion Sort and show the array after every pass.