Merge Two Sorted Arrays

📌 Definition:

📖 Detailed Explanation:

Walk both arrays with two pointers, repeatedly taking the smaller front element, until one is exhausted; then append the remainder of the other. O(n + m) time. Concatenating and re-sorting works but wastes the existing order (O((n+m) log(n+m))).

💻 Solutions:

• Java
• JavaScript
• Python

public static 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;
}

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++]);
  return out.concat(a.slice(i), b.slice(j));
}

def merge(a, b):
    out, i, j = [], 0, 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
    return out + a[i:] + b[j:]

🔑 Key Points:

• Two pointers, take the smaller front each step
• Append leftovers when one side ends
• O(n + m) — do not re-sort
• This is the merge step of merge sort

🌍 Real-World Example: