def merge(left, right):
    output = []
    il, ir = 0, 0
    while il < len(left) and ir < len(right):
        if left[il] < right[ir]:
            output.append(left[il])
            il += 1
        else:
            output.append(right[ir])
            ir += 1
    if left[il:]:
        output.extend(left[il:])
    if right[ir:]:
        output.extend(right[ir:])
    return output

def mergeSort(A, k, alg):
    if len(A) <= k:
        return alg(A)
    middle = len(A) // 2
    left = mergeSort(A[:middle], k, alg)
    right = mergeSort(A[middle:], k, alg)
    return merge(left, right)

def insertionSort(lst):
    temp = 0
    for i in range(0, len(lst)):
        for j in range (0, len(lst)):
            if(lst[i] < lst[j]):
                temp = lst[i]
                lst[i] = lst[j]
                lst[j] = temp
    return lst

def binarySearch(lst, item, Low, High):

    if Low == High:
        if lst[Low] > item:
            return Low
        else:
            return Low + 1

    if Low > High:
        return Low

    mid = (Low+High)//2

    if lst[mid] < item:
        return binarySearch(lst, item, mid+1, High)
    elif lst[mid] > item:
        return binarySearch(lst, item, Low, mid-1)
    else:
        return mid


def bSort(lst):
    for i in range(1, len(lst)):
        item = lst[i]
        j = binarySearch(lst, item, 0, i - 1)
        lst = lst[:j] + [item] + lst[j:i] + lst[i+1:]
    return lst