def merge(array, start, mid, end):
    tmp = []

    p1, p2 = start, mid+1
    for i in range(len(end-start+1)):
        if p1 > mid:
            tmp.append(array[p2])
            p2 += 1
        elif p2 > end:
            tmp.append(array[p1])
            p1 += 1
        elif array[p1] < array[p2]:
            tmp.append(array[p1])
        else:
            tmp.append(array[p2])

    array[start:end+1] = copy.deepcopy(tmp)


def merge_sort(array, start, end):

    if start < end:
        mid = start + (end - start)/2
        merge(array, start, mid)
        merge(array, mid+1, end)

    merge(start, mid, end)