병합 정렬 (Merge Sort)

한 줄 정의: 전체 데이터를 더 이상 나눌 수 없을 때까지 절반씩 쪼갠 뒤, 정렬된 조각들을 순서에 맞게 다시 합쳐 나가는 정렬 알고리즘입니다.

쉽게 풀면

섞여 있는 트럼프 카드 100장을 정렬한다고 해봅시다. 병합정렬은 이 카드 더미를 50장씩 두 뭉치로 나누고, 그 뭉치를 다시 25장씩 나누는 식으로 계속 반으로 쪼갭니다. 결국 카드 한 장짜리 더미까지 나뉘면(한 장은 이미 정렬된 상태나 마찬가지입니다), 이제 거꾸로 두 장씩 짝지어 "작은 카드부터 순서대로" 합치고, 그렇게 합친 뭉치끼리 또 순서대로 합치는 과정을 반복합니다. 이렇게 "쪼개고(분할) → 합친다(정복)"를 반복하면 전체가 정렬된 하나의 더미로 완성되는데, 이 과정은 항상 O(n log n) 시간이 걸리고 두 정렬된 조각을 합칠 임시 공간이 추가로 필요하다는 특징이 있습니다.

왜 중요한가

병합정렬은 최악의 경우에도 O(n log n) 성능이 보장되고 안정 정렬 특성을 갖추고 있어, 성능 예측이 중요한 실시간 시스템이나 값이 같은 항목의 순서 유지가 필요한 데이터 처리 파이프라인에서 즐겨 사용됩니다. 또한 분할정복이라는 알고리즘 설계 전략을 가장 직관적으로 보여주는 예시이기 때문에, 알고리즘 복잡도 분석과 병렬·외부 정렬 연구의 기초 개념으로도 반복적으로 인용됩니다.

논문에서는 이렇게 쓰입니다

"제안 알고리즘은 병합정렬 기반의 전처리 단계를 거쳐 시간복잡도 O(n log n)을 유지하면서도 안정 정렬(stable sort) 특성을 보장하였다."

이 문장은 "이 알고리즘은 병합정렬을 이용해 데이터를 미리 정리하는데, 속도가 O(n log n)으로 일정하고 값이 같은 데이터끼리의 원래 순서도 흐트러지지 않는다"는 뜻입니다.

"대규모 로그 데이터를 여러 서버에 분산 저장한 뒤 각 서버에서 병합정렬로 지역 정렬을 수행하고, 이를 다시 하나로 병합하여 전체 정렬 결과를 얻었다."

분산 데이터 처리 연구에서, 병합정렬의 병합 단계 아이디어를 이용해 여러 컴퓨터에 나뉜 대용량 데이터를 효율적으로 하나의 정렬 결과로 합치는 방식을 설명합니다.

"두 정렬된 리스트의 교집합·차집합을 계산하는 연산을 병합정렬의 병합 과정과 유사한 선형 시간 알고리즘으로 구현하였다."

자료구조·알고리즘 연구에서, 병합정렬의 핵심 아이디어인 "정렬된 두 리스트를 한 번의 순회로 합치는" 원리가 정렬 외의 집합 연산에도 응용될 수 있음을 보여주는 문장입니다.

조금 더 깊게 보면

병합정렬을 실제로 구현할 때는 재귀 호출로 나누는 하향식(top-down) 방식과, 크기가 작은 블록부터 순차적으로 합쳐 올라가는 상향식(bottom-up) 방식이 흔히 비교됩니다. 또한 병합 단계에서 추가로 필요한 임시 배열의 공간 복잡도(O(n))는 제자리 정렬(in-place)인 퀵정렬이나 힙정렬과 성능을 비교할 때 자주 언급되는 트레이드오프로, 메모리 제약이 큰 환경에서는 병합정렬 적용 여부를 신중히 검토하게 만드는 요인으로 다뤄집니다.

주의할 점

병합정렬은 값이 같은 원소들의 상대적 순서를 그대로 보존하는 안정 정렬이지만, 두 조각을 합치는 과정에서 원본과 같은 크기의 임시 배열이 추가로 필요합니다. 큰 문제를 절반씩 나누어 해결한 뒤 다시 합친다는 접근 방식 자체는 분할정복 전략의 대표적인 적용 사례입니다.