Please use Q1 below to answer Q2 in Python. Use a large data set of your choice and a simple time efficiency program (time taken = end time - start time) to test. Thanks!

Q1) Although merge sort runs in \Theta(n\lg n)(nlgn) worst-case time and insertion sort runs in \Theta(n^2)(n2) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/kn/k sublists of length kk are sorted using insertion sort and then merged using the standard merging mechanism, where kk is a value to be determined 2) Write a code combining both algorithms as described in Q1) to find out the most optimal K minimizing time efficiency of your algorithms using 1 M data set from HW2. You may use the time efficiency program you wrote in the previous home work. Please collect and display some performance data proving your K is the most optimal as shown below: K-5: 11.07 seconds K: 10.55 seconds K+5: 10.59 seconds. Please note that the efficiency data above are all made up by me for this homework purpose only. They are not actual simulation results. Q1) Although merge sort runs in \Theta(n\lg n)(nlgn) worst-case time and insertion sort runs in \Theta(n^2)(n2) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/kn/k sublists of length kk are sorted using insertion sort and then merged using the standard merging mechanism, where kk is a value to be determined 2) Write a code combining both algorithms as described in Q1) to find out the most optimal K minimizing time efficiency of your algorithms using 1 M data set from HW2. You may use the time efficiency program you wrote in the previous home work. Please collect and display some performance data proving your K is the most optimal as shown below: K-5: 11.07 seconds K: 10.55 seconds K+5: 10.59 seconds. Please note that the efficiency data above are all made up by me for this homework purpose only. They are not actual simulation results