Skip to content

10.01. Sorted Merge

Description

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Initially the number of elements in A and B are m and n respectively.

Example:

Input:

A = [1,2,3,0,0,0], m = 3

B = [2,5,6],       n = 3



Output: [1,2,2,3,5,6]

Solutions

Solution 1: Two Pointers

Thinking

\(B\) must merge into the spare tail of \(A\). Writing from the front overwrites unread values of \(A\). A third buffer uses linear extra space.

The unused suffix of \(A\) can hold the whole result, so placing the larger tail element first leaves the unread prefixes intact.

Pointers \(i\) and \(j\) sit at the live ends; \(k\) walks \(m+n-1\) downward. Write \(A[i]\) when \(B\) is exhausted or \(A[i]\) is larger, otherwise \(B[j]\).

We use two pointers \(i\) and \(j\) to point to the end of arrays \(A\) and \(B\) respectively, and a pointer \(k\) to point to the end of array \(A\). Then we traverse arrays \(A\) and \(B\) from back to front, each time putting the larger element into \(A[k]\), then moving pointer \(k\) and the pointer of the array with the larger element forward by one position.

The time complexity is \(O(m + n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        i, j = m - 1, n - 1
        for k in reversed(range(m + n)):
            if j < 0 or i >= 0 and A[i] > B[j]:
                A[k] = A[i]
                i -= 1
            else:
                A[k] = B[j]
                j -= 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1, j = n - 1;
        for (int k = A.length - 1; k >= 0; --k) {
            if (j < 0 || (i >= 0 && A[i] > B[j])) {
                A[k] = A[i--];
            } else {
                A[k] = B[j--];
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        int i = m - 1, j = n - 1;
        for (int k = A.size() - 1; ~k; --k) {
            if (j < 0 || (i >= 0 && A[i] > B[j])) {
                A[k] = A[i--];
            } else {
                A[k] = B[j--];
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func merge(A []int, m int, B []int, n int) {
    i, j := m-1, n-1
    for k := len(A) - 1; k >= 0; k-- {
        if j < 0 || (i >= 0 && A[i] > B[j]) {
            A[k] = A[i]
            i--
        } else {
            A[k] = B[j]
            j--
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 Do not return anything, modify A in-place instead.
 */
function merge(A: number[], m: number, B: number[], n: number): void {
    let [i, j] = [m - 1, n - 1];
    for (let k = A.length - 1; ~k; --k) {
        if (j < 0 || (i >= 0 && A[i] > B[j])) {
            A[k] = A[i--];
        } else {
            A[k] = B[j--];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn merge(a: &mut Vec<i32>, m: i32, b: &mut Vec<i32>, n: i32) {
        let (mut i, mut j) = (m - 1, n - 1);
        for k in (0..m + n).rev() {
            if j < 0 || (i >= 0 && a[i as usize] > b[j as usize]) {
                a[k as usize] = a[i as usize];
                i -= 1;
            } else {
                a[k as usize] = b[j as usize];
                j -= 1;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} A
 * @param {number} m
 * @param {number[]} B
 * @param {number} n
 * @return {void} Do not return anything, modify A in-place instead.
 */
var merge = function (A, m, B, n) {
    let [i, j] = [m - 1, n - 1];
    for (let k = A.length - 1; ~k; --k) {
        if (j < 0 || (i >= 0 && A[i] > B[j])) {
            A[k] = A[i--];
        } else {
            A[k] = B[j--];
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    func merge(_ A: inout [Int], _ m: Int, _ B: [Int], _ n: Int) {
        var i = m - 1, j = n - 1
        for k in stride(from: m + n - 1, through: 0, by: -1) {
            if j < 0 || (i >= 0 && A[i] > B[j]) {
                A[k] = A[i]
                i -= 1
            } else {
                A[k] = B[j]
                j -= 1
            }
        }
    }
}

Comments