Python

1. Implement a merge sort algorithm in Python. Modify the code, so that it prints the following:

The initial input sequence to be sorted, and its length. The order of the elements in the sequence, after the merge step has been performed on all the elements. Print this for every recursion depth, in the order the merges are performed. The total number of comparison operations performed during the run of the algorithm (a comparison operation is when 2 array elements are compared).

For instance, if the input array is [5, 3, 1, 2, 8, 4, 7, 6], you should print:

INPUT: 5,3,1,2,8,4,7,6 (length 8) MERGE STEP 1: 3,5,1,2,4,8,6,7 MERGE STEP 2: 1,2,3,5,4,6,7,8 MERGE STEP 3: 1,2,3,4,5,6,7,8 COMPARISONS: 14

Note that the number of comparisons will depend not only on the input given, but the specific way you implement merge sort, so you may get a slightly different number than above.

its output on the following input test cases: Array of numbers 1, 2, . . . , 50 (already in correct sorted order) Array of numbers 50, 49, . . . , 1 (reverse of correct sorted order) Array of 50 different random numbers