JavaScript로 정렬된 두 배열 병합하기

두 개의 정렬된 배열(오름차순)이 다음과 같이 주어져 있다고 가정해 보겠습니다.

const arr1 = [1, 2, 3, 0, 0, 0];
const arr2 = [2, 5, 6];

여기서 첫 번째 배열 끝의 0은 두 번째 배열의 요소가 들어갈 자리를 미리 확보해 둔 빈 공간입니다. 우리는 이렇게 주어진 두 배열을 받아 모든 요소를 정렬된 상태로 담고 있는 새로운 배열을 반환하는 JavaScript 함수를 작성해야 합니다.

따라서 위 배열에 대한 기대 출력은 다음과 같습니다.

const output = [1, 2, 2, 3, 5, 6];

방법 1: 배열을 합친 후 정렬하기

가장 직관적인 방법은 두 배열의 유효한 요소를 하나로 합친 뒤, sort() 메서드로 오름차순 정렬하는 것입니다.

const arr1 = [1, 2, 3, 0, 0, 0];
const arr2 = [2, 5, 6];

const mergeSortedArrays = (nums1, m, nums2) => {
  // 앞쪽의 유효한 요소(m개)만 잘라내어 두 번째 배열과 병합
  return nums1.slice(0, m).concat(nums2).sort((a, b) => a - b);
};

console.log(mergeSortedArrays(arr1, 3, arr2));

콘솔에 출력되는 결과는 다음과 같습니다.

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

이 방법은 구현이 매우 간단하다는 장점이 있지만, 시간 복잡도가 O((m+n) log(m+n))이므로 배열의 크기가 커질수록 성능이 떨어질 수 있습니다.

방법 2: 투 포인터(Two Pointer)로 효율적으로 병합하기

두 배열이 이미 정렬되어 있다는 특성을 활용하면 불필요한 재정렬 없이 한 번의 순회만으로 병합할 수 있습니다. 핵심 아이디어는 배열의 뒤에서부터 큰 값부터 차례로 채워 넣는 것입니다.

const mergeSortedArrays = (nums1, m, nums2, n) => {
  let i = m - 1;      // nums1의 마지막 유효 요소 인덱스
  let j = n - 1;      // nums2의 마지막 요소 인덱스
  let k = m + n - 1;  // 병합 결과가 저장될 위치

  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
  return nums1;
};

const arr1 = [1, 2, 3, 0, 0, 0];
const arr2 = [2, 5, 6];
console.log(mergeSortedArrays(arr1, 3, arr2, 3));

실행 결과 역시 동일하게 정렬된 배열이 반환됩니다.

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

마무리

두 배열을 단순히 합쳐 정렬하는 방식은 코드가 짧고 이해하기 쉽지만, 정렬 과정에 추가 비용이 발생합니다. 반면 투 포인터 기법은 이미 정렬된 배열의 특성을 그대로 활용하므로 시간 복잡도 O(m+n)으로 더욱 효율적입니다. 코딩 테스트나 대용량 데이터를 다루는 실무 환경에서는 투 포인터 방식을 사용하는 것이 좋습니다.