SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Merge Two Sorted Arrays Visualizer

Keep a pointer at the front of each array. Take the smaller of the two front values, move that pointer, and repeat. When one array runs out, copy the rest of the other.

Start the Merge Two Sorted Arrays simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n + m)
Average timeO(n + m)
Worst timeO(n + m)
Extra spaceO(n + m)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Indexes 0 to 3 are the first array, the rest the second. Each is sorted. [1, 4, 7, 9, 2, 3, 8, 10, 12]
  2. 1 ≤ 2: take 1 from the first array.
  3. 2 < 4: take 2 from the second array.
  4. 3 < 4: take 3 from the second array.
  5. 4 ≤ 8: take 4 from the first array.
  6. 7 ≤ 8: take 7 from the first array.
  7. 8 < 9: take 8 from the second array.
  8. 9 ≤ 10: take 9 from the first array.
  9. The first array is used up. Copy 10.
  10. The first array is used up. Copy 12.
  11. Done: 1, 2, 3, 4, 7, 8, 9, 10, 12.

Try it with your own input →

Merge two sorted arrays in Java, Python, C++, C and JavaScript

int[] merge(int[] a, int[] b) {
  int[] out = new int[a.length + b.length];
  int i = 0, j = 0, k = 0;
  while (i < a.length && j < b.length)
    out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
  while (i < a.length) out[k++] = a[i++];
  while (j < b.length) out[k++] = b[j++];
  return out;
}
def merge(a, b):
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out
vector<int> merge(const vector<int>& a, const vector<int>& b) {
  vector<int> out(a.size() + b.size());
  size_t i = 0, j = 0, k = 0;
  while (i < a.size() && j < b.size())
    out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
  while (i < a.size()) out[k++] = a[i++];
  while (j < b.size()) out[k++] = b[j++];
  return out;
}
void merge(int a[], int na, int b[], int nb, int out[]) {
  int i = 0, j = 0, k = 0;
  while (i < na && j < nb)
    out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
  while (i < na) out[k++] = a[i++];
  while (j < nb) out[k++] = b[j++];
}
function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length)
    out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

In an interview

LeetCode 88, Merge Sorted Array: combine two sorted arrays into one sorted array.

This is the merge step of merge sort. In LeetCode 88 the answer goes into nums1, so fill it from the back: the empty slots are at the end and nothing gets overwritten.

More patterns