Merge sorted array

Back to index

From the LeetCode problem with the same name. The problem statement is:

Given two sorted integer arrays `nums1` and `nums2`, merge `nums2` into `nums1` as one sorted array.

The number of elements initialised in `nums1` and `nums2` are `m` and `n` respectively. You may assume that `nums1` has a size equal to `m+n` such that it has enough space to hold additional elements from `nums2`.

When we are adding elements to an array we should overwrite the end of the array first and work backwards. Since we know that `nums1` has `n` zero entries at the end we can place the largest numbers at the end without overwriting data before we move it.

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    for (int i = m + n - 1; i >= 0; i--) {
      if (p1 < 0) {
        nums1[i] = nums2[p2];
        p2--;
        continue;
      }
      if (p2 < 0) {
        nums1[i] = nums1[p1];
        p1--;
        continue;
      }

      int greatest1 = nums1[p1];
      int greatest2 = nums2[p2];
      if (greatest1 < greatest2) {
        nums1[i] = nums2[p2];
        p2--;
        continue;
      } else {
        nums1[i] = nums1[p1];
        p1--;
      }
    }
  }
}