There is a key note to be made about the implementation of merge sort: it is ideal if we write the function to change the array in place.

The merge sort function itself will not return an array (instead it will modify the input array in place) but the merge procedure will create a copy of the two halves of the array to merge them.

Here is a canonical implementation:

def mergeSort(array):
    if len(array) > 1:
        mid = len(array) // 2
        L = array[:mid]
        M = array[mid:]

        mergeSort(L)
        mergeSort(M)

        i = 0
        j = 0
        k = 0

        while i < len(L) and j < len(M):
            if L[i] < M[j]:
                array[k] = L[i]
                i += 1
            else:
                array[k] = M[j]
                j += 1
            k += 1

        while i < len(L):
            array[k] = L[i]
            i += 1
            k += 1

        while j < len(M):
            array[k] = M[j]
            j += 1
            k += 1

if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]
    mergeSort(array)
    print("Sorted array is: ", end="")
    for i in range(len(array)):
        print(array[i], end=" ")
    print()

Time Complexity

Merge sort is an algorithm where a bulk of the work is done in the conquer (merge) step, leading to the recurrence:

$$ T(n)=2T(n/2)+n $$

Space Complexity

The auxiliary space complexity will be $O(n)$.

Example Problems