test_merge_sort.py

__author__ = 'Jeremy Chen'


def merge_sort(unsorted):

    sorted_ = []
    length = len(unsorted)
    if length == 1:
        sorted_ = unsorted

    elif length == 2:
        left = unsorted[:length//2]
        right = unsorted[length//2:]

        if left[0] >= right[0]:
            sorted_ = right + left
        else:
            sorted_ = left + right

    elif length == 3:
        left_sorted = merge_sort(unsorted[:length//2])
        right_sorted = merge_sort(unsorted[length//2:])

        if left_sorted[0] <= right_sorted[0]:
            sorted_.append(left_sorted[0])
            sorted_.append(right_sorted[0])
            sorted_.append(right_sorted[1])

        elif left_sorted[0] <= right_sorted[1]:
            sorted_.append(right_sorted[0])
            sorted_.append(left_sorted[0])
            sorted_.append(right_sorted[1])
        else:
            sorted_.append(right_sorted[0])
            sorted_.append(right_sorted[1])
            sorted_.append(left_sorted[0])

    elif length >= 4:
        left_sorted = merge_sort(unsorted[:length//2])
        right_sorted = merge_sort(unsorted[length//2:])

        l, r = 0, 0
        for i in range(length):
            if l == len(left_sorted):
                sorted_.append(right_sorted[r])
                r += 1
            elif r == len(right_sorted):
                sorted_.append(left_sorted[l])
                l += 1
            elif left_sorted[l] < right_sorted[r]:
                sorted_.append(left_sorted[l])
                l += 1
            else:
                sorted_.append(right_sorted[r])
                r += 1
    return sorted_



def test_one_num():
    assert merge_sort([1]) == [1]

def test_two_nums():
    assert merge_sort([1, 2]) == [1, 2]
    assert merge_sort([2, 1]) == [1, 2]
    assert merge_sort([4, 3]) == [3, 4]

def test_three_nums():
    assert merge_sort([1, 2, 3]) == [1, 2, 3]
    assert merge_sort([1, 3, 2]) == [1, 2, 3]
    assert merge_sort([2, 1, 3]) == [1, 2, 3]
    assert merge_sort([2, 3, 1]) == [1, 2, 3]
    assert merge_sort([3, 1, 2]) == [1, 2, 3]
    assert merge_sort([3, 2, 1]) == [1, 2, 3]


def test_any_nums():
    assert merge_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    assert merge_sort([99, 34, 3, -19, -8, 7, 45]) == [-19, -8, 3, 7, 34, 45, 99]