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]

## No comments:

## Post a Comment