Merge sort

Algorithm

def mergesort(a):
    """
    Implements the merge sort algorithm.
    """

    def merge(a, low, mid, high):
        i = low
        j = mid + 1
        aux = a[low:high+1]     # aux is 0-indexed and (the interesting part of) a is low-indexed.
                                # Example: aux[0:3] == a[7:10]

        for k in range(low, high+1):

            # Left half exhausted => Take from the right
            if i > mid:
                a[k] = aux[j - low]
                j = j + 1

            # Right half exhausted => Take from the left
            elif j > high:
                a[k] = aux[i - low]
                i = i + 1

            # Key on right < key on left => Take from the right
            elif aux[j - low] < aux[i - low]:
                a[k] = aux[j - low]
                j = j + 1

            # Key on left <= key on right => Take from the left
            else:
                a[k] = aux[i - low]
                i = i + 1

    def sort(a, low, high):
        if high <= low:
            return

        mid = low + ((high - low)//2)
        sort(a, low, mid)
        sort(a, mid+1, high)
        merge(a,low,mid,high)

    sort(a, 0, len(a)-1)
    return a

In the merge function we use three indices:

i to pick elements from the first (left) half of the array.
j to pick elements from the last (right) half of the array.
k to move through the a array.

Step by step

array = [1,0,3,4,2,5]

sort([1, 0, 3, 4, 2, 5],0,2)
    sort([1, 0, 3, 4, 2, 5],0,1)
        sort([1, 0, 3, 4, 2, 5],0,0)
        sort([1, 0, 3, 4, 2, 5],1,1)
        merge([1, 0, 3, 4, 2, 5],0,0,1) | array = [0,1,3,4,2,5]
    sort([0, 1, 3, 4, 2, 5],2,2)
    merge([0, 1, 3, 4, 2, 5],0,1,2)
sort([0, 1, 3, 4, 2, 5],3,5)
    sort([0, 1, 3, 4, 2, 5],3,4)
        sort([0, 1, 3, 4, 2, 5],3,3)
        sort([0, 1, 3, 4, 2, 5],4,4)
        merge([0, 1, 3, 4, 2, 5],3,3,4) | array = [0,1,3,2,4,5]
    sort([0, 1, 3, 2, 4, 5],5,5)
    merge([0, 1, 3, 2, 4, 5],3,4,5)
merge([0, 1, 3, 2, 4, 5],0,2,5)         | array = [0,1,2,3,4,5]

Complexity analysis

Time

In each step we reduce the elements in half, so we have log N levels. In each level we sort the left half (O(N) = 1), sort the right half (O(N) = 1) and we merge the 2 halves. To merge the halves, in the worst case, we do 2N access to the arrays to copy the elements, 2N access to the arrays to move back the data and 2N compares.

So the cost is: O(N) = 6N · log N ≈ N · log N.

Space

We use the same array that is passed as argument and another one that holds a copy of some elements of the array. In the worst case the auxiliary array holds as many elements as the original array, so the cost is: O(N) = N + N = 2N ≈ N.

Use cases

This algorithm is specially useful for sorting linked lists because it does not rely on random access to elements.

A bottom-up approach

We can also see the mergesort algorithm in a bottom-up approach. In this approach, we go first all the way down to merging arrays of size 1, then arrays of size 2, then arrays of sife 4, etc. In the last step we will merge two arrays with a size of approximately N/2.

Instead of splitting our array in two halves, we go down until we have arrays of size 1 and merge them to double their size.

def mergesortBU(a):
    """
    Implements the merge sort algorithm with a bottom-up approach.
    """

    def merge(a, low, mid, high):
        [...]

    def sort(a, low, high):

        size = 1
        while size < len(a):
            low = 0
            while low < (len(a) - size):
                mid = low + size - 1
                high = min(low + size + size - 1, len(a) - 1)
                merge(a,low,mid,high)
                low = low + 2 * size
            size = 2 * size

    sort(a, 0, len(a)-1)
    return a