병합 정렬
병합 정렬은 어려운 문제 하나를 쉬운 문제 여러 개로 바꿉니다. 정렬된 두 목록은 하나로 합치기 쉽기 때문입니다. 모든 조각이 값 하나가 될 때까지 목록을 반으로 나눈 뒤, 조각들을 다시 병합합니다. 대표적인 분할 정복 알고리즘이며, 입력과 상관없이 시간은 n log n입니다.
기본 아이디어
병합은 쉬운 부분입니다. 각각 정렬된 두 목록이 있으면 첫 값끼리 비교해 더 작은 값을 가져옵니다. 새로운 첫 값끼리 비교해 다시 더 작은 값을 가져옵니다. 한 목록이 바닥나면 다른 목록의 나머지를 뒤에 붙입니다. 매 단계 값 하나를 가져오므로, 전체 길이가 m인 두 목록을 병합하는 데는 많아야 m − 1번의 비교가 필요합니다. 병합 정렬은 이를 이용해 정렬합니다. 목록을 반으로 나누고, 각 절반을 병합 정렬로 정렬한 뒤, 두 절반을 병합합니다.
예시
5, 1, 4, 2, 8을 예로 들어 봅시다. 이를 5, 1과 4, 2, 8로 나눕니다. 앞 절반은 5와 1로 나뉘고, 병합하면 1, 5가 됩니다. 뒤 절반은 4와 2, 8로 나뉩니다. 2, 8은 2와 8을 병합한 것이고, 다시 4와 병합해 2, 4, 8이 됩니다. 마지막으로 1, 5와 2, 4, 8을 병합합니다. 1, 2, 4, 5 순으로 가져오고 8이 남습니다. 비교 8번, 쓰기 12번, 병합 4번입니다.
왜 n log n인가
나눌 때마다 조각이 절반이 되므로, 약 log₂ n 단계 뒤에는 모든 조각이 값 하나가 됩니다. 다시 올라가면서 단계마다 병합이 모든 값을 한 번씩 처리하므로, 단계당 쓰기는 n번, 비교는 n번 미만입니다. 합치면 약 n log₂ n입니다. 값 40개일 때 정렬은 216번 쓰고 많아야 177번 비교합니다. 같은 목록에 버블 정렬은 780번 비교가 필요할 수 있습니다. 입력 순서의 영향도 그런 정렬보다 훨씬 적습니다. 값 40개일 때 정렬된 목록은 100번, 역순 목록은 116번, 무작위 목록은 약 160번 비교합니다.
버퍼와 안정성
목록에서 나란히 있는 두 절반을 병합하려면, 보통 이들을 버퍼로 복사한 뒤 순서대로 다시 씁니다. 이 앱은 그 버퍼를 두 번째 줄의 막대로 보여 줍니다. 목록만큼의 추가 메모리가 필요하며, 이것이 병합 정렬의 가장 큰 비용입니다. 그 대신 안정 정렬입니다. 두 맨 앞 값이 같으면 왼쪽 절반의 값이 먼저 가므로, 같은 값들은 순서를 유지합니다. 안정성은 레코드를 여러 필드로 차례로 정렬할 때 중요합니다.
역사와 활용
John von Neumann은 1945년에 병합 정렬을 설명했으며, 이는 프로그램 내장식 컴퓨터를 위해 작성된 최초의 알고리즘 중 하나입니다. 데이터를 긴 연속 구간으로 읽고 쓰기 때문에 테이프의 데이터를 정렬하는 표준 방법이었고, 지금도 메모리에 다 들어가지 않는 큰 파일에 쓰입니다. Python과 Java(객체 정렬)에서 쓰는 Timsort는 이미 정렬된 구간을 먼저 찾고 짧은 조각에는 삽입 정렬을 쓰는 병합 정렬입니다.
직접 살펴보기
앱을 열고 ‘단계’를 누르세요. 목록에서 음영이 있는 부분이 나뉘거나 병합되는 중이며, 점선은 가운데를 표시합니다. 병합이 시작되면 두 절반이 버퍼 줄로 내려가고, 두 맨 앞 값을 비교해 더 작은 값이 다시 올라갑니다. 카운터를 지켜보세요. 쓰기 횟수는 길이가 같은 목록이면 모두 같고, 비교 횟수는 정렬되었거나 역순인 목록에서 가장 적고 무작위 목록에서 가장 많지만, 약 n log₂ n을 넘지 않습니다.
자주 묻는 질문
병합 정렬의 시간 복잡도는 얼마인가요?
최선, 평균, 최악의 경우 모두 O(n log n)입니다. 보통의 구현은 버퍼를 위해 O(n)의 추가 메모리가 필요합니다.
병합 정렬과 퀵 정렬은 어떻게 다른가요?
둘 다 목록을 나누고 각 부분을 정렬합니다. 병합 정렬은 값을 보지 않고 가운데에서 나누며, 병합할 때 일을 합니다. 퀵 정렬은 나눌 때 피벗을 기준으로 값을 옮기며 일을 하고, 병합이 필요 없습니다. 퀵 정렬은 제자리 정렬이고 실제로는 더 빠를 때가 많지만, 나쁜 입력에서는 n²까지 느려질 수 있고 안정 정렬이 아닙니다. 병합 정렬은 언제나 n log n이고 안정 정렬입니다.
상향식 병합 정렬이란 무엇인가요?
재귀를 쓰지 않는 방식입니다. 먼저 이웃한 값 하나씩을 병합해 쌍을 만들고, 쌍을 병합해 넷씩 묶는 식으로 매번 길이를 두 배로 늘립니다. 여기서 보여 주는 하향식 방식과 같은 양의 일을 합니다.
병합 정렬은 안정 정렬인가요?
네. 이 앱처럼 값이 같을 때 왼쪽 절반의 값을 먼저 가져오면 안정 정렬입니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
병합 정렬 해 보기