Binary Insertion Sort : An efficient improvement over Insertion Sort

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Algorithm
Complexity
Implementations
Discussions

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


 #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;
}