×

Search anything:

Binary Insertion Sort

Learn Algorithms and become a National Programmer
Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

Binary search is used to reduce the number of comparisons in Insertion sort. This modification is known as Binary Insertion Sort.

Binary Insertion Sort use binary search to find the proper location to insert the selected item at each iteration. In insertion sort, it takes O(i) (at ith iteration) in worst case. Using binary search, it is reduced to O(log i).

Complexity

  • Worst case time complexity: Θ(N log N) comparisons and swaps
  • Average case time complexity: Θ(N log N) comparisons and swaps
  • Best case time complexity: Θ(N) comparisons and Θ(1) swaps
  • Space complexity: Θ(1).

Implementation

Implementation of Binary Insertion Sort algorithm in 1 language that includes C.

  • C

C


 #include <stdio.h>
int binary_search(int a[], int item, int low, int high)
{
    if (high <= low)
        return (item > a[low])?  (low + 1): low;
    int mid = (low + high)/2;
    if(item == a[mid])
        return mid+1;
    if(item > a[mid])
        return binary_search(a, item, mid+1, high);
    return binary_search(a, item, low, mid-1);
}
void insertion_sort(int a[], int n)
{
    int i, location = 0, j, k, selected, n = sizeof(a)/sizeof(a[0]);
    for (i = 1; i < n; ++i)
    {
        j = i - 1;
        selected = a[i]; 
        location = binary_search(a, selected, 0, j);
        while (j >= location)
        {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = selected;
    }
}
int main()
{
    int a[] = {1,2,5,6,3,9,1};
    int i = 0;
    insertionSort(a);
    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ",a[i]);
    return 0;
}
Alexa Ryder

Alexa Ryder

Hi, I am creating the perfect textual information customized for learning. Message me for anything.

Read More

Vote for Author of this article:

Improved & Reviewed by: