배열을 절반씩 쪼개 각각 정렬한 뒤 합치는 정렬. 분할 정복의 교과서적인 예이고, 분할 정복을 이해하기에 가장 좋은 알고리즘이기도 하다.
쪼개고 합치기
배열을 반으로 나누고, 각 절반을 같은 방식으로 정렬하고, 정렬된 두 조각을 앞에서부터 비교하며 합친다. 재귀는 시작 인덱스와 끝 인덱스가 같아질 때 멈춘다. 원소가 하나면 그 자체로 정렬된 상태라 더 쪼갤 필요가 없다.
흔들리지 않는 n log n
최선도 평균도 최악도 O(n log n)이다. 최악에도 n log n이 보장된다는 것이 퀵 정렬과의 결정적 차이다. 쪼개는 깊이가 log n이고 각 깊이에서 전체 n개를 한 번씩 훑으니 곱해서 n log n인데, 어떤 입력을 줘도 절반씩 정확히 나뉘므로 이 값이 흔들리지 않는다.
왼쪽을 먼저 가져가는 안정성
합칠 때 두 값이 같으면 왼쪽 조각의 것을 먼저 가져가도록 구현하면 순서가 유지되어 안정 정렬이 된다. 자바의 객체 정렬이 합병 계열을 택한 것도 그래서인데, 어떤 구현인지는 안정 정렬에 적어두었다.
임시 배열이 필요한 이유
공간복잡도가 O(n)이다. 합치는 단계에서 결과를 담을 임시 배열이 필요하고 그 크기가 원소 수에 비례하니 제자리 정렬이 아니다. 메모리를 더 쓰기 싫으면 퀵 정렬을 쓴다는 선택지가 여기서 나온다.
거꾸로, 메모리에 다 안 들어가는 데이터를 조각내 각각 정렬하고 합치는 외부 정렬은 합병 정렬의 합치는 단계를 그대로 빌려 쓴다.