To speed up the running time of insertion sort we can attemp

To speed up the running time of insertion sort, we can attempt to use a binary search to search for the insertion point. The idea is the following: We are searching a sorted area (see Ex.2-5 in notes) for the insertion point. Currently, we are using a linear search, we would instead like to use a binary search to find the insertion point. What is the running time of the new algorithm? You should include an (English) argument with your conclusion.

Solution

The Binary Insertion Sort Algorithm name suggested, this is the Insertion sort but we use binary search instead of linear search for finding the appropriate place of the inserting element.

The algorithm is the following:

Binary_Search (A [0...N-1], value, low, high)

{                                                                       

      if (high <= low)

        return (item > a[low])? (low + 1): low;

    int mid = (low + high)/2;

    if(item == a[mid])

        return mid+1;//à return position where item to be inserted

    if(item > a[mid])

        return Binary_Search (a, item, mid+1, high);

    return Binary_Search (a, item, low, mid-1);

  }

INSERTION-SORT(A)
   for j = 1 to n
   key A [j]
      // Insert A[j] into the sorted sequence A[1..j-1]
   j i – 1

Selected=a[i];

loc = Binary_Search (a, selected, 0, j);

. while j>=loc
   A[i+1] A[i]
   j j – 1
   A[j+1] selected

There is an outer loop through the list (with j ranging from 2 to n - 1). Inside this outer loop, there are main lines

1)- loc = Binary_Search (a, selected, 0, j) is used for finding the right position for the node to whom we want to insert

2)-: while loop is used for to move all elements after location to create space

Now I will start by analyzing the complexity of the binary search portion, in terms of comparisons made. Then, I will analyse the complexity of the code that swaps the integers.

For each value of key the Binary_Search algorithms is called and it’s executed log(n) time

As we know the Binary_Search have log (n) time complexity for each node

Now we focus on INSERTION-SORT ()

The outer for loop will be executed O(n) time for each value of the j(key) the Binary_Search function will be called and return the suitable position within log(n) time the position will be stored in the loc variable this while loop is for finding the correct position in the worst case this loop is executing O(n) time lets us assume the condition where j is pointing the last index and we want to insert node whose loc position is at index 1 or 0 so while loop will be executed n time

The total Complexity is O(n²)

But the algorithm reduces the total number of comparison ie. O(logn)

please write me if you have any doubt regarding the solution