Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In each iteration, insertion sort inserts an element into an already sorted list (on left). The...

use python to solve this question

Extracted text: Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In each iteration, insertion sort inserts an element into an already sorted list (on left). The position where the item will be inserted is found through linear search. You decided to improve insertion sort by using binary search to find the position p where the new insertion should take place. Algorithm BinarylnsertionSort Input/output: takes an integer array a = {a[0], ..., a[n - 1]} of size n begin BinarylnsertionSort for i =1 to n val = a[i] p= BinarySearch(a, val, 0, i – 1) for j = i-1 to p alj + 1]= a[j] J=J-1 end for a[p] = val i= i+1 end for end BinarylnsertionSort Here, val = a[i] is the current value to be inserted at each step i into the already sorted part a[0], . .., a[i - 1] of the array a. The binary search along that part returns the position p where the val will be inserted. After finding p, the data values in the subsequent positions j = i- 1, ... , p are sequentially moved one position up to i, ... inserted into the proper position p. ,p+1 so that the value val can be