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

mergeSort(arr)

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.

mergeSort(arr) = (
    merge(
        mergeSort(left half of arr),
        mergeSort(right half of arr)
    )
)

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

mergeSort(arr) = (
    mid = len(arr) // 2 # divide length by 2 and round down in case it's a fraction
    leftHalf = arr[:mid+1]
    rightHalf = arr[mid+1:]

    return merge(
        mergeSort(leftHalf),
        mergeSort(rightHalf)
    )
)

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:

if len(arr) == 0 or len(arr) == 1:
    return arr # array is already sorted

3. Code

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

def mergeSort(arr):
    # base case
    if len(arr) == 0 or len(arr) == 1:
        return arr
    
    # recursion
    mid = len(arr) // 2
    sortedL = mergeSort(arr[:mid+1])
    sortedR = mergeSort(arr[mid+1:])
    return merge(sortedL, sortedR)

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

def merge(arr1, arr2):
    i = 0 # leftmost index in `arr1` that we haven't used
    j = 0 # leftmost index in `arr2` that we haven't used

    solution = [] # the blank solution array

    # keep adding the smaller of the leftmost elements to `solution`
    while i != len(arr1) and j != len(arr2):
        if arr1[i] < arr2[j]:
            solution.append(arr1[i])
            i += 1
        else:
            solution.append(arr2[j])
            j += 1

    # once we've used all the elements in an array, add all the remaining elements from the other array
    for i2 in range(i,len(arr1)): solution.append(arr1[i2])
    for j2 in range(j,len(arr2)): solution.append(arr2[j2])
    
    return solution




def mergeSort(arr):
    # base case
    if len(arr) == 0 or len(arr) == 1:
        return arr
    
    # recursion
    mid = (len(arr) - 1) // 2
    sortedL = mergeSort(arr[:mid+1])
    sortedR = mergeSort(arr[mid+1:])
    return merge(sortedL, sortedR)

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

Open SpoilerClose Spoiler

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

Open SpoilerClose 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.