Binary Insertion Sort Program with Explanation and Code

2025-11-19 binary insertion sort optimized insertion sort binary search sorting data structures sorting algorithms python binary insertion sort c binary insertion sort javascript binary insertion sort php binary insertion sort csharp binary insertion sort

Binary Insertion Sort improves normal insertion sort by using Binary Search to find the correct insertion position, reducing comparisons. This page includes the full explanation and code examples in Python, C, JavaScript, PHP, and C#, ideal for students and interviews.

Program Explanation

What is Binary Insertion Sort?

Binary Insertion Sort is an optimized version of Insertion Sort that uses Binary Search to find the correct position of an element in the sorted part of the array. Instead of linearly searching for the insertion point, Binary Search reduces the number of comparisons from O(n) to O(log n).

Steps to Solve

  1. Start from the second element of the array.
  2. Use Binary Search to find the correct index where the current element should be inserted.
  3. Shift all elements to the right to make space for the new element.
  4. Insert the element at the correct position.
  5. Repeat the process for all elements in the array.
  6. The array becomes sorted as each element is placed correctly.

Key Points

  • Improves comparison count using Binary Search.
  • Still requires shifting elements → O(n²) time in the worst case.
  • Works well for small and nearly sorted datasets.
  • Stable sorting algorithm.
  • In-place sorting → no extra memory required.

Program Code


def binary_search(arr, key, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] > key:
            end = mid - 1
        else:
            start = mid + 1
    return start

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        pos = binary_search(arr, key, 0, i - 1)
        arr[pos+1:i+1] = arr[pos:i]
        arr[pos] = key

arr = list(map(int, input("Enter numbers: ").split()))
binary_insertion_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

int binarySearch(int arr[], int item, int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (item < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

void binaryInsertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int pos = binarySearch(arr, key, 0, i - 1);

        for (int j = i - 1; j >= pos; j--)
            arr[j + 1] = arr[j];

        arr[pos] = key;
    }
}

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

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

    binaryInsertionSort(arr, n);

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

    return 0;
}
      

function binarySearch(arr, key, low, high) {
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] > key) high = mid - 1;
    else low = mid + 1;
  }
  return low;
}

function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let pos = binarySearch(arr, key, 0, i - 1);

    for (let j = i - 1; j >= pos; j--)
      arr[j + 1] = arr[j];

    arr[pos] = key;
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
binaryInsertionSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static int BinarySearch(int[] arr, int key, int low, int high) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    static void BinaryInsertionSort(int[] arr) {
        for (int i = 1; i < arr.Length; i++) {
            int key = arr[i];
            int pos = BinarySearch(arr, key, 0, i - 1);

            for (int j = i - 1; j >= pos; j--)
                arr[j + 1] = arr[j];

            arr[pos] = key;
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        BinaryInsertionSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function binarySearch($arr, $key, $low, $high) {
    while ($low <= $high) {
        $mid = intdiv($low + $high, 2);

        if ($arr[$mid] > $key)
            $high = $mid - 1;
        else
            $low = $mid + 1;
    }
    return $low;
}

function binaryInsertionSort(&$arr) {
    $n = count($arr);

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

        for ($j = $i - 1; $j >= $pos; $j--)
            $arr[$j + 1] = $arr[$j];

        $arr[$pos] = $key;
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
binaryInsertionSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1