In Python

Implement a merge sort algorithm in your favorite programming language $($e$.$g$.$

C$,$ Java, Python, etc.$).$ 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.

Submit a print out of your code, and its output on the following input test cases:

Array of numbers $1,2,$dots,$50($already in correct sorted order$)$

Array of numbers $50,49,$dots,$1($reverse of correct sorted order$)$

Array of $50$ different random numbers