Binary Insertion Sort Overview with Pseudo Code and Examples

Binary search is also called binary insertion sort and is based on the binary search algorithm. Developers often confuse it with the typical insertion sort which works on the liner search algorithm. It is important to note that simple insertion sort is less efficient when compared with binary insertion sort. 

The complexity of a simple insertion sort that uses linear sort is O(N) but with binary search, it reduces to O(log N)T.

How Does Binary Insertion Sort work?

In a binary search algorithm, the input array is divided into two parts, one of which is always sorted (new array) and the other one is unsorted (input array to start with). 

The first element of the input array is added to the sorted array as the first element and all other elements stay in the second unsorted array. The algorithm iterates through the sorted array and performs a binary search for each element of the unsorted array to find its correct position in the sorted array. Let us understand with an example –

Understanding Binary Insertion Sort with Example:

Consider this array [5, 2, 4, 6, 1, 3], the algorithm starts by picking the first element and moves it to a separate array (we are calling it our sorted array). In this example, the sorted array will start off with 5 as the first element [5], and the unsorted array will be left with the rest of the elements – [2, 4, 6, 1, 3].

The sorting algorithm will then pick the next element from the unsorted array, which is 2, and will run the binary search on the sorted array to find the correct position for element 2. In our example, the correct position of 2 is before 5, so the algorithm will add 2 in the sorted array, to the left of 5, and the sorted array would become [2, 5], and the unsorted array would be left with [4,6,1,3]. 

The algorithm will continue with the next element of the unsorted array, which now is 4, and would run the binary search on the sorted array, which is [2,5]. The position of 4 falls before 5 as per the binary search, so the algorithm will move 5 to the right to create a space for 4 and insert the element to make the array look like [2,4,5]. This continues till all elements and so on till all elements from the unsorted array move to the sorted array. The final sorted array will become [1,2,3,4,5,6]

When to Use Binary Insertion Sort?

While there are many faster sorting algorithms but there are still scenarios where you can use insertion sort with binary search efficiently, as mentioned below- 

• When the array size is small, binary search is effective and hence the overall sorting. Other sorting algorithms like merge sort and quick sort typically come with an overhead as compared to binary sort and hence are not too effective in small-sized arrays. 
• If the array is already heavily sorted, binary search effectively finds the correct position of the next element making overall sorting faster. 
• In some scenarios, you continue to get a stream of real-time data elements, in that scenario also binary insertion sort works well. This is because you start off with a smaller data set and progressively keep adding additionally retrieved data in the already sorted data set. 

You should avoid binary insertion sort when the array size is large or the elements are randomly placed. There are many other computation and memory-efficient algorithms you can look at. 

The Complexity of Binary Insertion Sort Algorithm

Let us look at time complexity and space complexity which also relate to computation power usage and memory usage respectively. The time complexity of the insertion algorithm with binary sort is O(n*log(n)), where n is the number of elements in the array. This complexity comes from the fact that the algorithm performs a binary search to find the correct position of every element of the input array, and O(log(n)) is the time taken per search.

The space complexity on the other hand is O(1) which essentially means that the algorithm uses constant memory irrespective of the input array size, so this shouldn’t really be a consideration for developers. The complexity of other sorting algorithms like bubble sort and insertion sort is O(n^2) and hence binary insertion sort stands better than those. Having said that, algorithms like quicksort and merge sort are much more efficient with the complexity of O(n*log(n)).

The above complexity is based on the generic scenario, if we look at best case scenario for binary insertion sort where the array is already sorted (of course you don’t know but for the algorithm it is), it would come out to be O(n) because the algorithm doesn’t shift any element. The worst-case scenario would be O(n*log(n)) where the input array is completely in reverse order.

Pseudo Code for Insertion Sort with Binary Search

Given below is a small piece of pseudo code depicting how you can write a binary insertion sort algorithm in any programming language.

procedure my_bin_ins_sort(A: list of sortable items)
    for i = 1 to length(A) - 1
        j = i
        key = A[i]
        left = 0
        right = i
        while left < right
            middle_val = (left + right) / 2
            if key < A[middle_val]
                right = middle_val
            else
                left = middle_val + 1
        end while
        while j > left
            A[j] = A[j - 1]
            j = j - 1
        end while
        A[left] = key
    end for
end procedure

Developers typically use binary sort on an array of integers but you must take care of a few things when writing the binary insertion sort on integers in various programming languages.

For example, in the C programming language, if you are running binary insertion sort on a list of integers, then the middle_val (check pseudo code above) which is the division of two integers would result in an integer after rounding. To take care of this, you should either cast the operand to float or use the modulus operator % to get the remainder that should be added to the division result.

In JavaScript, the Math.floor() is used in the middle_val calculation to round off the result since JavaScript uses floating-point numbers to represent decimal values. Given below is the sample code for binary insertion sort in JavaScript, it is similar to the Pseudo code except for the use of Math.floor().

function JS_BinInsSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let left = 0;
        let right = i;
        while (left < right) {
            let middle_val = Math.floor((left + right) / 2);
            if (key < arr[middle_val]) {
                right = middle_val;
            } else {
                left = middle_val + 1;
            }
        }
        for (let j = i; j > left; j--) {
            arr[j] = arr[j - 1];
        }
        arr[left] = key;
    }
    return arr;
}

Hope this clarifies your understanding of the Binary insertion sort. Do share with your friends if you like this brief overview of the insertion sort with binary search algorithm.

Conclusion

There are many algorithms like mega sort, quick sort, merge sort, insertion sort, binary sort, etc. It is important to understand which one fits best in your use case.

Choosing the wrong algorithm can significantly impact memory usage, and overall time to do sorting and would waste server computation power too.