We'll solve this problem by creating a recursive function called mergeSort.

1. Recursion

Sorting the whole array is the same thing as sorting the left half and the right half and then merging them together using the merge function.

You can convert this idea into code pretty easily. Here's the code:

2. Base case

The recursion keeps calling mergeSort on smaller and smaller arrays. To find the base case, just check when the recursion breaks by looking at the smallest arrays. If we call the recursion on a size 3 or size 2 array it works fine, but when we call it on a size 1 and size 0 array it breaks. So those are the base cases:

3. Code

To code the solution, just combine the recursion and base case. The code for merge comes from the Merge problem.

Here's the full code, including the merge function:

Time Complexity $O(n \log n)$, equal to the total number of operations done by merge. See below.

Open Spoiler

Space Complexity $O(n)$. See spoiler for details - can be reduced to $O(1)$ using advanced ideas.

Open Spoiler

merge takes up a single $O(n)$ cost in total, since when we're done merging two arrays we immediately discard the input arrays.

The Call Stack gets $O(\log n)$ calls tall. Each call in it uses memory, since it stores sortedL as it waits to compute sortedR. If you add up the whole cost of the Call Stack including the calls in it, you get a total of $O(n)$ memory, since the size of sortedL halves as you go down the tree, giving a cost of $\frac{n}{2}+\frac{n}{4}+\frac{n}{8}...=n$.

Below shows the worst-case example of memory usage at any point. If you count all the boxes, it's O(n).

It's possible to get MergeSort down to $O(1)$ space by modifying the original array in-place. This requires not using recursion so that you avoid the Call Stack space, which you can do by merging the arrays in the correct order in as if you were doing Dynamic Programming.

You also need to make $\tt merge$ be in-place which is difficult. It's called "Block Sort".

Just for fun, we took the above recursion and turned it into a picture. The gray boxes are function calls and the arrows are inputs/outputs. People get those crazy pictures of MergeSort by expanding the mergeSort boxes all the way down to the base case.