JavaScript로 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 방법

이번 글에서는 숫자로 이루어진 두 개의 정렬된 배열을 인자로 받아, 두 배열을 하나로 합친 뒤에도 정렬 상태가 유지되는 결과 배열을 만들어 반환하는 JavaScript 함수를 작성해 보겠습니다.

문제 이해하기

예를 들어 다음과 같은 두 개의 정렬된 배열이 있다고 가정해 보겠습니다.

const arr1 = [2, 6, 6, 8, 9];
const arr2 = [1, 4, 5, 7];

이 두 배열을 병합하면 최종 출력은 다음과 같아야 합니다.

const output = [1, 2, 4, 5, 6, 6, 7, 8, 9];

접근 방식: 뒤에서부터 채우는 투 포인터 기법

두 배열이 이미 정렬되어 있으므로, 처음부터 순서대로 비교하는 대신 배열의 끝에서부터 더 큰 값을 찾아 결과 배열의 마지막 위치부터 채워 넣는 것이 효율적입니다. 이 방식을 사용하면 별도의 결과 배열을 새로 만들 필요 없이 첫 번째 배열(arr1) 안에서 제자리(in-place) 병합을 수행할 수 있으며, 전체 시간 복잡도는 O(m + n)입니다.

구현 코드

const arr1 = [2, 6, 6, 8, 9];
const arr2 = [1, 4, 5, 7];

const mergeSortedArrays = (arr1 = [], arr2 = []) => {
    let m = arr1.length;
    let n = arr2.length;
    let currentIndex = m + n;
    const checkNum1HasLargerNumber = (a, b) => {
        if (a < 0) {
            return false;
        };
        if (b < 0) {
            return true;
        };
        return arr1[a] >= arr2[b];
    };
    m -= 1;
    n -= 1;
    while (currentIndex--) {
        let hasNums1LargerNumber = checkNum1HasLargerNumber(m, n);
        arr1[currentIndex] = hasNums1LargerNumber ? arr1[m] : arr2[n];
        if (hasNums1LargerNumber) {
            m -= 1;
        } else {
            n -= 1;
        }
    };
};
mergeSortedArrays(arr1, arr2);
console.log(arr1);

실행 결과

콘솔에는 다음과 같이 병합된 정렬 배열이 출력됩니다.

[
    1, 2, 4, 5, 6,
    6, 7, 8, 9
]

코드 동작 원리

m, n: 각각 arr1과 arr2의 마지막 요소 인덱스를 가리키는 포인터입니다.
currentIndex: 병합된 값이 저장될 위치로, 두 배열 길이의 합(m + n)에서 시작해 매 반복마다 1씩 감소합니다.
checkNum1HasLargerNumber(): 두 배열의 현재 값을 비교하는 헬퍼 함수입니다. arr1의 인덱스가 0 미만이면(모든 요소 소진) false를, arr2의 인덱스가 0 미만이면 true를 반환하고, 그 외에는 arr1[a] >= arr2[b]의 비교 결과를 반환합니다.
while 루프: 매 반복마다 더 큰 값을 currentIndex 위치에 배치하고, 해당 값을 사용한 배열의 포인터(m 또는 n)를 앞으로 이동시킵니다.

한쪽 배열의 요소를 모두 소진하더라도 헬퍼 함수가 이를 자동으로 처리해 주므로, 남은 요소들이 올바른 순서대로 채워집니다. 이 알고리즘은 '정렬된 배열'이라는 전제 조건을 활용해 단일 패스(one-pass)로 병합을 완료하기 때문에, 단순히 concat() 후 sort()를 호출하는 O((m+n) log(m+n)) 방식보다 성능 면에서 유리합니다.