插入与归并

def solve(original, partial):
    original = list(map(int, original.split(",")))
    partial = list(map(int, partial.split(",")))
    n = len(original)
    for i in range(1, n):
        if partial[:i+1] == sorted(partial[:i+1]) and partial[i+1:] == original[i+1:]:
            print("Insertion Sort")
            nxt = partial[:]
            if i + 1 < n:
                key = original[i+1]
                nxt[i+1] = key
                j = i
                while j >= 0 and nxt[j] > key:
                    nxt[j+1] = nxt[j]
                    j -= 1
                nxt[j+1] = key
            print(" ".join(map(str, nxt)))
            return
    print("Merge Sort")
    seg = 1
    while True:
        seg *= 2
        prev = []
        for i in range(0, n, seg // 2):
            prev += sorted(original[i:i + seg // 2])
        if prev == partial:
            nxt = []
            for i in range(0, n, seg):
                nxt += sorted(original[i:i + seg])
            print(" ".join(map(str, nxt)))
            return
        if seg >= n * 2:
            break