Implement a method to sort a given array using the merge sort algorithm. You can use the algorithm provided $($see Page $2)$ instead of the algorithm from the textbook.

Write a driver program to test the merge sort algorithm for the arrays of varying lengths provided in Canvas.

Compare the execution time of merge sort with insertion sort implemented in Lab$-2.$ Make sure you use the same array to compare the performance. Use a table or plot to summarize the results and document your fibservations and analysis in the report.

Based on the performance results obtained in Problem$-3,$ modify the merge sort algorithm such that when the array size gets small enough, you would invoke insertion sort instead of invoking merge sort $($hint: you have to change the base condition in the recursion$).$ Instead of hardcoding the array size make it a variable that you can pass as an argument to the merge sort method and test this cutoff value with at least four different values.

Test the program for the same array sizes and values. Compare the performance with the original merge sort implementation, plot the execution times, and document the analysis in your lab report.

$//$ NOTE: You have to allocate temp array in the main method and copy the original input array $A$ to $//$ the temp array before invoking merge sort in the main method.

MERGE$-$SORT $(A,$ temp, $p,r)$

$ifp$