Implement function BinaryInsertionSort that takes an unsorted array as a parameter and returns a sorted array.

Language: Python 3

Refrain from using any inbuilt functions and importing modules.

Provide code and attach screenshots.

>>> BinaryInsertionSort([37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]) [0, 12, 17, 23, 31, 37, 46, 54, 72, 88, 100] >>> BinaryInsertionSort([5, 2, 7, 10, 3, 5, 2, 1, 8, 9]) [1, 2, 2, 3, 5, 5, 7, 8, 9, 10]

3. Hybrid Sort Language: Python 3 Autocomplete Ready O C 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. 1 v import ast 2 Ist = input() 3 Ist = ast.literal_eval(lst) 4 5 def Binary InsertionSort(lst): 6 7 print(Binary InsertionSort(lst)) Algorithm BinaryInsertion Sort Input/output: takes an integer array a = {a[0], ..., a[n - 1]} of size n begin BinaryInsertion Sort for i =1 to n val = a[i] p = BinarySearch(a, val, 0, i -1) for j = 1-1 to p a[j + 1]= a[j] j=j-1 end for a[p] = val i = i + 1 end for end BinaryinsertionSort Here, val = a[i] is the current value to be inserted at each step i into the already sorted part a[O],..., 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, ..., p+1 so that the value val can be inserted into the proper position p. Line: 6 Col: 1 Implement function Binary InsertionSort that takes an unsorted array as a parameter and returns a sorted array. Test Results Custom Innut Run Code Run Tests Submit