Hiprup

How do you merge two sorted arrays?

Combine two already-sorted arrays into one sorted array.

  1. Use two pointers, one per array.

  2. Compare the current items and push the smaller one, advancing that pointer.

  3. When one array is exhausted, append the rest of the other.

Efficient: this two-pointer merge is O(n) — better than concatenating and re-sorting (O(n log n)).

function mergeSorted(arr1, arr2) {
  const result = [];
  let i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.push(arr1[i++]);
    } else {
      result.push(arr2[j++]);
    }
  }

  // Add remaining elements
  while (i < arr1.length) result.push(arr1[i++]);
  while (j < arr2.length) result.push(arr2[j++]);

  return result;
}

console.log(mergeSorted([1, 3, 5, 7], [2, 4, 6, 8]));
// [1, 2, 3, 4, 5, 6, 7, 8]

console.log(mergeSorted([1, 2], [3, 4, 5, 6]));
// [1, 2, 3, 4, 5, 6]

// One-liner (not optimal but concise)
const merge = (a, b) => [...a, ...b].sort((x, y) => x - y);
// O(n log n) — slower than the two-pointer approach

Two pointers (i, j) compare elements from both arrays. The smaller element is pushed to the result and its pointer advances. After one array is exhausted, the remaining elements of the other are appended.

O(n+m) time — optimal because each element is processed exactly once. The sort-based one-liner is O(n log n) — slower.

The two-pointer approach is O(n+m) — optimal. Show the loop structure: compare, push smaller, advance pointer.

The remaining-elements step (while loops at the end) handles unequal lengths. This is the merge step of merge sort — mention this connection.

How do you merge two sorted arrays? | Hiprup