병합 정렬

병합 정렬은 배열을 효율적으로 정렬하기 위해 사용되는 대표적인 분할 정복(divide and conquer) 알고리즘이다. 큰 문제를 한 번에 해결하려 하지 않고, 작은 문제로 계속 쪼갠 뒤 정렬하고 다시 합치는 방식으로 동작한다. 병합 정렬이 강력한 이유는 이 구조 덕분에 어떤 입력이 들어와도 시간 복잡도가 일정하게 유지된다는 점이다.

정렬 과정은 크게 두 단계로 나뉜다. 먼저 분할 단계에서는 배열을 길이가 1이 될 때까지 반으로 계속 쪼갠다. 예를 들어 [8, 3, 5, 1]이라는 배열이 있다면, 이를 [8, 3]과 [5, 1]로 나누고, 다시 [8]·[3], [5]·[1]처럼 계속 절반으로 나눈다. 길이가 1인 배열은 이미 정렬된 상태이므로 더 이상 쪼갤 필요가 없다.

그다음은 병합 단계다. 이 단계에서는 쪼개진 배열들을 두 개씩 비교하며 정렬된 형태로 합친다. 예를 들어 [8]과 [3]을 합칠 때는 두 값을 비교해 [3, 8]이 되고, [5]와 [1]은 [1, 5]가 된다. 이렇게 정렬된 두 배열을 다시 병합하면 최종적으로 [1, 3, 5, 8]이라는 정렬된 결과가 완성된다. 핵심은 “각 부분 배열이 이미 정렬되어 있으므로 병합 과정에서 앞 요소끼리만 비교하면 된다”는 점이다. 이 때문에 병합 정렬의 병합 단계는 매우 효율적으로 동작한다.

병합 정렬을 이해할 때 가장 중요한 포인트는 항상 배열을 반으로 나눈 뒤 합치는 과정이 같은 패턴으로 반복된다는 것이다. 이 구조는 배열이 어떤 상태로 들어오든 변하지 않는다. 완전히 정렬된 배열이든, 완전히 뒤죽박죽된 배열이든, 절반으로 나누는 횟수는 똑같고 병합하는 과정도 동일하게 반복된다. 이러한 특징 때문에 병합 정렬의 시간 복잡도는 입력 상황에 관계없이 항상 O(n log n)이다.

여기서 log n이 등장하는 이유는 분할 단계 때문이다. 배열을 반씩 나누다 보면, 길이가 n이면 log₂n 번 나누면 길이 1이 된다. 분할 단계는 log n 만큼 발생한다. 그리고 병합할 때는 매 단계에서 전체 요소 n개를 모두 한 번씩 비교하거나 복사하게 된다. 따라서 전체 시간 복잡도는 n(log n)이 된다. 정렬 알고리즘에서 n log n은 매우 빠른 축에 속하며, 버블 정렬이나 삽입 정렬처럼 n²이 필요한 알고리즘보다 훨씬 효율적이다.

병합 정렬은 공간을 더 사용하는 편이라는 단점도 있다. 병합 과정에서 두 배열을 새로운 배열에 담아 합치는 과정이 필요하기 때문에, 추가적인 메모리 공간이 필요하고 공간 복잡도는 O(n)이 된다. 하지만 이 비용을 감수하더라도, 안정적이고 일정한 속도로 빠른 정렬이 필요할 때 병합 정렬은 매우 강력한 선택이다.

병합 정렬은 구조가 명확하고 시간 복잡도가 일정하다는 장점 덕분에, 실제 많은 프로그래밍 언어의 기본 정렬 알고리즘 내부에서도 사용된다(예: Python의 Timsort는 병합 정렬과 삽입 정렬을 조합한 방식이다). 즉, 단순히 알고리즘을 배우기 위한 개념을 넘어, 실전에서도 널리 활용되는 정렬 방식이다.