Mergesort is a complicated process, but what is it actually doing? We are going to take a closer look at the process in this exercise.

You are given the merge sort algorithm and you need to add some print statements so that you can see what actually is happening.

Add a print statement at each step, as well as print out the array each time. Your output needs to match the sample below. Here is a portion of a sort as an example:

Unsorted: $758349126$

Splitting $...$

$***$ Left Half: $7583$

$***$ Right Half: $49126$

Splitting $...$

$***$ Left Half: $75$

$***$ Right Half: $83$

Splitting $...$

$***$ Left Half: $7$

$***$ Right Half: $5$

Merging $...$

$***$ Sorted so Far: $57$

$...$

Merging $...$

$***$ Sorted so Far: $126$

Merging $...$

$***$ Sorted so Far: $12469$

Merging $...$

$***$ Sorted so Far: $123456789$

Sorted: $123456789$