def merge_sort(arr):
    """
    Returns the list 'arr' sorted in nondecreasing order in O(nlogn) time.
    """
    r = len(arr)
    if 1 < len(arr):
        q = int(r/2)
        L = merge_sort(arr[0:q])
        R = merge_sort(arr[q:])

        print(L,R)
        i,j,k = 0,0,0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i = i+1
                k = k+1
            elif R[j] < L[i]:
                arr[k] = R[j]
                j = j+1
                k = k+1
        if i >= len(L):
            while j < len(R):
                arr[k] = R[j]
                j = j+1
                k = k+1
        elif j >= len(R):
            while i < len(L):
                arr[k] = L[i]
                i = i+1
                k = k+1

    print(arr,'\n')
    return arr