Binary Sort (Binary Insertion Sort)

Binary Sort is also known as Binary Insertion Sort. It is a variation of the Insertion Sort algorithm.

The only difference is that instead of scanning the sorted portion linearly to find the correct position for insertion, it uses Binary Search to find the position, making the search faster.

In Binary Insertion Sort, the number of comparisons is reduced by using binary search, but the number of shifts remains the same as normal Insertion Sort.

How Does It Work?

1. Start from the second element in the array because the first element is already considered "sorted".
2. Find the correct position in the sorted left part of the array.
3. Binary search to quickly find where the key should be inserted
4. Use low and high pointers to define the current search range within the sorted part.
   1. Calculate the middle index (mid) using
      mid = (low + high) / 2
   2. Compare the key with the element at mid
      • If key < arr[mid], it must go to the left, so move high = mid - 1
      • If key > arr[mid], it must go to the right, so move low = mid + 1
   3. Repeat this until low > high. At this point, low is the correct insert position.
5. Shift all elements to the right to make space for the key.
6. Insert the key at the position low.
7. Repeat steps for all remaining elements in the array.

Example: Binary (Insertion) Sort

Let’s solve the array {37, 23, 0, 17, 12, 72, 31} using Binary Insertion Sort, pass by pass, in clear and detailed explanation.

Initial Array is {37, 23, 0, 17, 12, 72, 31}

We’ll insert each element (from index 1 to 6) into the correct position in the sorted part using binary search, and then shift elements to insert.

Pass 1 (i = 1, key = 23)

Sorted part: [37]

Use binary search to find where to insert 23 in [37].

• low = 0, high = 0
• mid = (0 + 0) / 2 = 0
• 23 < 37 → high = mid - 1 = -1
• Now low = 0, high = -1 → stop
• Insert at position low = 0
• Shift 37 right

Array now: [23, 37, 0, 17, 12, 72, 31]

Pass 2 (i = 2, key = 0)

Sorted part: [23, 37]

Binary search for 0:

• low = 0, high = 1
• mid = (0 + 1) / 2 = 0
• 0 < 23 → high = mid - 1 = -1
• low = 0, high = -1 → stop
• Insert at position low = 0
• Shift 23 and 37 right

Array now: [0, 23, 37, 17, 12, 72, 31]

Pass 3 (i = 3, key = 17)

Sorted part: [0, 23, 37]

Binary search for 17:

• low = 0, high = 2
• mid = (0 + 2) / 2 = 1
• 17 < 23 → high = mid - 1 = 0
• mid = (0 + 0) / 2 = 0
• 17 > 0 → low = mid + 1 = 1
• low = 1, high = 0 → stop
• Insert at position low = 1
• Shift 23 and 37 right

Array now: [0, 17, 23, 37, 12, 72, 31]

Pass 4 (i = 4, key = 12)

Sorted part: [0, 17, 23, 37]

Binary search for 12:

• low = 0, high = 3
• mid = (0 + 3) / 2 = 1
• 12 < 17 → high = mid - 1 = 0
• mid = (0 + 0) / 2 = 0
• 12 > 0 → low = mid + 1 = 1
• low = 1, high = 0 → stop
• Insert at position low = 1
• Shift 17, 23, 37 right

Array now: [0, 12, 17, 23, 37, 72, 31]

Pass 5 (i = 5, key = 72)

Sorted part: [0, 12, 17, 23, 37]

Binary search for 72:

• low = 0, high = 4
• mid = (0 + 4) / 2 = 2
• 72 > 17 → low = mid + 1 = 3
• mid = (3 + 4) / 2 = 3
• 72 > 23 → low = mid + 1 = 4
• mid = (4 + 4) / 2 = 4
• 72 > 37 → low = mid + 1 = 5
• low = 5, high = 4 → stop
• Insert at position low = 5 (already there)

Array now: [0, 12, 17, 23, 37, 72, 31]

Pass 6 (i = 6, key = 31)

Sorted part: [0, 12, 17, 23, 37, 72]

Binary search for 31:

• low = 0, high = 5
• mid = (0 + 5) / 2 = 2
• 31 > 17 → low = mid + 1 = 3
• mid = (3 + 5) / 2 = 4
• 31 < 37 → high = mid - 1 = 3
• mid = (3 + 3) / 2 = 3
• 31 > 23 → low = mid + 1 = 4
• low = 4, high = 3 → stop
• Insert at position low = 4
• Shift 37 and 72 right

Final Sorted Array: {0, 12, 17, 23, 31, 37, 72}

Summary Table

Where to Use Binary Sort?

In educational tools to demonstrate optimisation techniques.

When binary search is already implemented.

For small or partially sorted data.

To combine search and sorting logic simply.

Time and Space Complexity

Advantages of Binary Sort

Fewer comparisons than normal insertion sort.

In-place sorting (no extra space needed).

Efficient on small or nearly sorted arrays.

Good for learning binary search and insertion concepts together.

Disadvantages of Binary Sort

O(n²) in worst case due to shifting.

Not suitable for large datasets.

Binary search doesn't help reduce shifting operations.

Algorithm for Binary Sort

Step 1: Repeat for i = 1 to n - 1
    - Take the value at index i → call it key
    - Set low = 0, high = i - 1

Step 2: Use Binary Search to find position
    - While low ≤ high
        - Set mid = (low + high) / 2
        - If key < arr[mid], set high = mid - 1
        - Else, set low = mid + 1
    - Now, low is the correct position to insert key

Step 3: Shift all elements from index i-1 to low
    - For j = i - 1 down to low
        - Move arr[j] to arr[j + 1]

Step 4: Place key at arr[low]

Step 5: Repeat until all elements are sorted

C Program for Binary Sort

#include <stdio.h>

// Binary Search to find position to insert
int binarySearch(int arr[], int item, int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (item == arr[mid])
            return mid + 1;
        else if (item > arr[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}

// Binary Insertion Sort Function
void binaryInsertionSort(int arr[], int n) {
    int i, j, pos, selected;

    for (i = 1; i < n; ++i) {
        selected = arr[i];
        pos = binarySearch(arr, selected, 0, i - 1);

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

        arr[pos] = selected;
    }
}

// Display Array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {37, 23, 0, 17, 12, 72, 31};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original Array:\n");
    printArray(arr, n);

    binaryInsertionSort(arr, n);

    printf("Sorted Array:\n");
    printArray(arr, n);

    return 0;
}

Output

Original array:
16 14 10 8 7 9 3 2 4 1
Sorted array using Heap Sort:
1 2 3 4 7 8 9 10 14 16

Why Is This Better Than Insertion Sort?

Normal Insertion Sort uses linear search to find position — O(n) time.

Binary Insertion Sort uses binary search — O(log n) time.

So it saves time when comparing large or complex data.

Numerical Questions for Binary Sort

1. Sort the following array using Binary Insertion Sort {29, 15, 10, 40, 7}. Show the steps of binary search and insertion at each pass.
2. Sort this array using Binary Insertion Sort {8, 4, 1, 56, 3, -44, 23, -6}. Show how the position of each element is found using binary search, and how elements are shifted.
3. Apply Binary Insertion Sort on {45, 12, 5, 78, 31, 6}. Show the array after each pass.
4. Sort the {22, 11, 99, 88, 9, 7, 42} using Binary Insertion Sort and count
   1. Number of comparisons
   2. Number of shifts
5. Given this array {34, 21, 13, 89, 55, 3}. Manually trace the binary search range for each pass and the final sorted array.