Question

Write an Insertion Sort algorithm that uses Binary Search to find the position where the next insertion should take place.

Short answer

The key to implementing Insertion Sort with Binary Search is to use Binary Search to find the position of the next insertion. The detailed process involves initializing the Insertion Sort function, picking the next element, applying Binary Search on the already sorted part to find the position for the next insertion, then moving all greater elements one position ahead and inserting the chosen element at its found position. Repeat these steps till the end of the array.

Step-by-step solution

Initialize Insertion Sort Function

First, the Insertion Sort function is defined. It takes an array as a parameter. Inside the function, there will be a loop running from the second element to the last element of the array. The reason for starting from the second element is that single element is already sorted.

Pick Next Element

For each iteration of the outer loop, an element from the array is chosen. The chosen element, which is key here, is like a card being picked from a deck and needs to be placed at correct position in the sorted part of the array.

Apply Binary Search

Now, Binary Search is performed on the sorted part of the array to find the correct position for the 'key'. If the 'key' is smaller than the middle element, the search continues in the lower half, else in the upper half. This process repeats until the correct position is found.

Move Elements and Insert Key

After getting the correct position, move all elements greater than 'key' to one position ahead to create space and then insert 'key' at its correct position.

Repeat for All Elements

Repeat the Step 2 to Step 4 for each element in the array till the array is sorted. After all elements have been iterated, the array is sorted.