# merge sort
# http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html

import pytest

def test_merge_sort():
    input1 = [31, 23, 43, 56, 9]
    input2 = []
    assert merge_sort(input1) == [9, 23, 31, 43, 56]
    assert merge_sort(input2) == []

def merge_sort(input):
    if len(input) > 1:
        mid = len(input)//2
        left = input[:mid]
        right = input[mid:]

        merge_sort(left)
        merge_sort(right)

        # in-place merge, the merge always starts from the left as
        # merge_sort(left) is called first
        i,j,k = 0,0,0
        # sync compare
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                input[k] = left[i]
                i += 1
            else:
                input[k] = right[j]
                j += 1
            k += 1
        # the larger ones
        while i < len(left):
            input[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            input[k] = right[j]
            j += 1
            k += 1
    return input