자바스크립트로 정렬된 두 배열을 하나의 정렬된 배열로 병합하는 방법

문제 소개

정렬되어 있는 두 개의 숫자 배열이 주어졌을 때, 두 배열의 모든 요소를 하나의 새로운 배열에 합치고, 기존과 동일한 정렬 순서를 유지한 채 결과 배열을 반환하는 자바스크립트 함수를 작성해야 합니다.

예를 들어 [1, 3, 4, 5, 6, 8]과 [4, 6, 8, 9, 11]이라는 두 배열이 있다면, 이 둘을 병합한 결과는 다음과 같아야 합니다.

[ 1, 3, 4, 4, 5, 6, 6, 8, 8, 9, 11 ]

접근 방식

두 배열이 이미 정렬되어 있다는 점이 핵심입니다. 이 경우 투 포인터(Two Pointer) 기법을 사용하면 효율적으로 병합할 수 있습니다.

알고리즘 동작 원리

각 배열의 시작 위치를 가리키는 두 개의 인덱스(i, j)를 준비합니다. 그런 다음 두 값을 비교하며 더 작은 쪽을 결과 배열에 추가하고 해당 포인터를 한 칸 앞으로 이동시킵니다. 한쪽 배열의 모든 요소가 처리되면, 나머지 배열에 남은 요소들을 그대로 이어 붙이면 됩니다.

이 방식은 각 요소를 한 번씩만 비교하므로 시간 복잡도는 O(n + m)(n, m은 각 배열의 길이)으로 매우 효율적입니다. 반면 단순히 두 배열을 합친 뒤 다시 정렬하는 방식은 O((n+m) log(n+m))이 걸리므로, 정렬된 배열을 다룰 때는 투 포인터 방식이 훨씬 유리합니다.

구현 코드

const arr1 = [1, 3, 4, 5, 6, 8];
const arr2 = [4, 6, 8, 9, 11];

const mergeSortedArrays = (arr1 = [], arr2 = []) => {
    const res = [];
    let i = 0;
    let j = 0;

    // 두 배열을 동시에 순회하며 작은 값부터 결과 배열에 추가
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            res.push(arr1[i]);
            i++;
        } else {
            res.push(arr2[j]);
            j++;
        }
    }

    // arr1에 남은 요소가 있다면 모두 추가
    while (i < arr1.length) {
        res.push(arr1[i]);
        i++;
    }

    // arr2에 남은 요소가 있다면 모두 추가
    while (j < arr2.length) {
        res.push(arr2[j]);
        j++;
    }

    return res;
};

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

실행 결과

[ 1, 3, 4, 4, 5, 6, 6, 8, 8, 9, 11 ]

마무리

이 알고리즘은 병합 정렬(Merge Sort)의 핵심 병합 단계와 동일한 원리로 동작합니다. 중복 값도 자연스럽게 함께 유지되며, 입력 배열의 크기에 관계없이 선형 시간 안에 처리할 수 있어 코딩 테스트나 실무에서 자주 활용되는 패턴입니다.