2-way merge (inplace)

from:
A[1..m]: {m elements sorted | n garbage elements}
B[1..n]: {n elements sorted}
get to:
A[1..m]: {m+n element sorted}
sort in-place.

Do a 2-way merge for sorted lists from the end. Assume lists are sorted ascendingly.

2wayMerge_inplace(int[] A, int[] B):
    m = A.length() - B.length()
    n = B.length()

    // merge 2 sorted lists
    a = m-1
    b = n-1
    target = m+n-1
    while (a >= 0 && b >= 0):
        if (A[a] > B[b]:
            A[target--] = A[a--]
        else
            A[target--] = B[b--]
            
    // if list has all elements greater than other
    while (b >= 0):
        A[target--] = B[b--]
    // A is already sorted so no need
    //while (a >= 0):
    //    A[target--] = A[a--]

O(m+n) time, in-place.

[Hat tip to IB]