def mergeSort(_list):
    n = len(_list)
    if (n > 1):
        mid = (n // 2)
        left = _list[:mid]
        right = _list[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while ((i < len(left)) and (j < len(right))):
            if (left[i] < right[j]):
                _list[k] = left[i]
                i += 1
            else:
                _list[k] = right[j]
                j += 1
            k += 1
        while (i < len(left)):
            _list[k] = left[i]
            i += 1
            k += 1
        while (j < len(right)):
            _list[k] = right[j]
            j += 1
            k += 1
def mergeSort(_list):
    n = len(_list)
    if (n > 1):
        mid = (n // 2)
        left = _list[:mid]
        right = _list[mid:]
        mergeSort(left)
        mergeSort(right)
        i = j = k = 0
        while ((i < len(left)) and (j < len(right))):
            if (left[i] < right[j]):
                _list[k] = left[i]
                i += 1
            else:
                _list[k] = right[j]
                j += 1
            k += 1
        while (i < len(left)):
            _list[k] = left[i]
            i += 1
            k += 1
        while (j < len(right)):
            _list[k] = right[j]
            j += 1
            k += 1