You are asked to compare the sorting algorithms below both empirically and theoretically. Use 1000 randomly generated arrays for each problem size (small (size = 100), medium (size = 1000), and large (size = 10000)). Empirical results should be obtained as the average of the 1000 independent runs for each algorithm and problem size individually. Please note that you must use the same set of arrays for testing/comparing algorithms. Analyze the execution time complexity of these algorithms theoretically. Evaluate the consistency between empirical and theoretical analysis results of the algorithms and explain your analysis results by supporting them with tables and diagrams. 1. Implement and evaluate the MergeSort algorithm. 2. Implement and evaluate the QuickSort algorithm. 3. Implement and evaluate the new_sort algorithm. Use the following pseudo-code to implement new_sort. #new_sort (array, head, tail) { IF (head > tail) ELSE { Return array; MIN, MAX = min_max_finder(array, head, tail); swap(array[head], array[MIN]); swap(array[tail], array[MAX]); Return new_sort(array, head + 1, tail -1); } * The min_max_finder() is a recursive function that returns the indices of minimum and maximum items between the given head and tail items in a single execution together. Don't implement this function by calling separate functions that find min and max items. Your recursive function should divide the problem into two almost equal size subproblems.