merge sort

Merge sorts will divide an array in half to sort each side independently using recursion. These are then merged together after the sorting is completed by adding each item from the array's halves into a new array in sorted order.

How it works

The algorithm breaks a list of items into sub-lists to sort recursively.

Each recursive call will create smaller sub-divided list objects that will be sorted through. Once finished, they are joined together in sorted order.

The merge sort does log n merge steps because each merge step doubles the list size. It does n work steps during merging because it looks at every item.

Runtime is O(nlogn)

Big-o

The merge sort runs in good time, O(nlogn). Merge sort uses O(n) space.

Example implementation

This implementation utilizes Python and is parametrized with Pytest.

def merge_sort(data_list: List[int]) -> None:
    merge_sort_recursive(data_list, 0, len(data_list) - 1)


def merge_sort_recursive(data_list: List[int], first: int, last: int) -> None:

    # find the middle of a list and break it up
    if first < last:
        middle = (first + last) // 2
        # break the left half of the list
        merge_sort_recursive(data_list, first, middle)

        # break the right half of the list
        merge_sort_recursive(data_list, middle + 1, last)

        # merge the halves
        merge(data_list, first, middle, last)


def merge(data_list: List[int], first: int, middle: int, last: int) -> None:
    left_half = data_list[first:middle + 1]
    right_half = data_list[middle + 1:last + 1]

    # sentinel values
    # these signal being done with the sorting
    left_half.append(99999999999)
    right_half.append(99999999999)

    i = 0
    j = 0

    for k in range(first, last + 1):
        if left_half[i] <= right_half[j]:
            data_list[k] = left_half[i]
            i += 1
        else:
            data_list[k] = right_half[j]
            j += 1


@pytest.mark.parametrize(
    "data_list",
    [
        ([]),
        ([1]),
        ([1, 2]),
        ([2, 2]),
        ([3, 2]),
        ([3, 2, 4, 8, 7]),
        ([3, 2, 4, 9, 7, 8]),
    ],
)
def test_merge_sort(data_list):
    merge_sort(data_list)

    length = len(data_list)
    for i in range(length-1):
        for j in range(0, length-i-1):
            assert data_list[j] <= data_list[j + 1]