python Interactive Sorting

interact_sort.py

# SK
# Interactive Sorting

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]
 
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2:
        testcase = input(f"? {L[i]} {R[j]}\n")
        if "<" in testcase:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
 
 
def mergeSort(arr, l, r):
    if l < r:
 
        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

# https://stackoverflow.com/questions/1534748/design-an-efficient-algorithm-to-sort-5-distinct-keys-in-fewer-than-8-comparison
# https://en.wikipedia.org/wiki/Merge-insertion_sort
def merge_insertion_manual(a, b, c, d, e):
    'Sort 5 values with 7 Comparisons'
    if ("<" in input(f"? {a} {b}\n")):      a, b = b, a
    if ("<" in input(f"? {c} {d}\n")):      c, d = d, c
    if ("<" in input(f"? {a} {c}\n")):      a, b, c, d = c, d, a, b
    if ("<" in input(f"? {e} {c}\n")):
        if ("<" in input(f"? {e} {d}\n")):  pass
        else:      d, e = e, d
    else:
        if ("<" in input(f"? {e} {a}\n")):  c, d, e = e, c, d
        else:      a, c, d, e = e, a, c, d
    if ("<" in input(f"? {b} {d}\n")):
        if ("<" in input(f"? {b} {e}\n")):  return b, e, d, c, a
        else:      return e, b, d, c, a
    else:
        if ("<" in input(f"? {b} {c}\n")):  return e, d, b, c, a
        else:      return e, d, c, b, a

mycharstr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
N, Q = map(int, input().split())
arr = [c for c in mycharstr[:N]]
if N == 5:
    res = merge_insertion_manual(*arr)
    print('! ' + ''.join(res))
else:
    mergeSort(arr, 0, N-1)
    print('! ' + ''.join(arr))