병합 삽입 정렬 (Ford-Johnson)

무엇을 최적화하나

병합 삽입 정렬(merge-insertion sort)은 1959년 Lester Ford Jr.와 Selmer Johnson이 발표한 정렬로, 원소끼리 비교하는 횟수를 줄이는 데 집중한다. 실행 시간은 퀵·병합 정렬보다 느리지만(원소 이동이 많다), 오랫동안 알려진 비교 정렬 중 최소 비교 횟수에 가장 가까웠다. 비교 한 번이 매우 비싼 상황(사람이 판정하는 비교, 원격 호출)이나 비교 횟수 자체를 평가하는 과제에서 의미가 있다.

알고리즘

n개 원소 X를 정렬한다.

1. 짝짓기: 원소를 둘씩 묶어 ⌊n/2⌋개 쌍을 만들고 각 쌍을 한 번씩 비교한다. n이 홀수면 하나가 남는다.
2. 큰 쪽 재귀 정렬: 각 쌍의 큰 원소들만 모아 같은 알고리즘으로 재귀 정렬한다. 정렬된 큰 원소를 a₁ < a₂ < … 로, 각 aᵢ의 짝인 작은 원소를 bᵢ로 부른다. 그러면 bᵢ < aᵢ가 보장된다.
3. 주 사슬(main chain) 만들기: b₁은 a₁보다 작고 a₁이 가장 작은 a이므로 비교 없이 맨 앞에 놓는다. 주 사슬은 b₁ a₁ a₂ a₃ …가 된다.
4. 나머지 b를 이진 삽입: b₂, b₃, …(그리고 남은 원소)를 주 사슬에 이진 탐색으로 끼워 넣는다. bᵢ는 aᵢ보다 작으므로 aᵢ 앞까지만 탐색하면 된다. 이 삽입 순서가 알고리즘의 핵심이다.

flowchart LR
  A["쌍 비교"] --> B["큰 원소만 재귀 정렬"] --> C["b1을 맨 앞에"] --> D["나머지 b를 정해진 순서로 이진 삽입"]

삽입 순서와 야콥스탈 수

정렬된 원소 m개 사이에 하나를 이진 삽입하려면 ⌈log₂(m + 1)⌉번 비교한다. m이 2ᵏ − 1 이하면 k번으로 끝나고, 2ᵏ개가 되는 순간 한 번이 더 든다. 그래서 각 b를 넣을 때 탐색 범위가 2ᵏ − 1개를 넘지 않도록 순서를 고른다.

• b₂를 먼저 넣으면 주 사슬이 b₁ a₁ b₂ a₂ a₃가 되고, b₃(< a₃)는 앞의 원소 4개 사이에서 찾아야 해 3번이 든다.
• b₃를 먼저 넣으면 b₃는 b₁ a₁ a₂ 3개 사이에서 2번에 끝난다. 이어서 b₂(< a₂)는 b₁ a₁과 경우에 따라 b₃까지, 많아야 3개 사이에서 역시 2번에 끝난다.
• 다음 묶음은 b₅, b₄(각 3번 이하), 그다음은 b₁₁ … b₆(각 4번 이하)다. 각 묶음 안에서는 번호가 큰 것부터 넣는다.

묶음의 경계가 되는 번호 1, 3, 5, 11, 21, 43, …는 야콥스탈 수(Jacobsthal number) 다.

J₀ = 0, J₁ = 1, Jₙ = Jₙ₋₁ + 2·Jₙ₋₂
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, …
 
일반항: Jₙ = (2ⁿ − (−1)ⁿ) / 3

삽입 순서는 b3 b2 | b5 b4 | b11 b10 … b6 | b21 … b12 | …가 된다. 묶음 크기는 2, 2, 6, 10, 22, …로, 각 묶음의 원소가 모두 같은 횟수(2, 3, 4, 5, …번)의 이진 탐색으로 들어간다. 구현할 때는 야콥스탈 수를 미리 계산해 경계로 쓰거나, "현재 탐색 범위가 2ᵏ − 1을 넘지 않는 가장 먼 b부터 넣는다"는 원리대로 직접 순서를 정해도 같다.

일반항을 점화식에서 유도하는 세 가지 방법(생성함수, 특성방정식, 행렬 대각화)은 선형 점화식의 일반항에 정리했다.

구현할 때 주의할 점

• 재귀 단계의 원소는 "쌍"이다. 깊이가 하나 내려갈 때마다 원소 하나가 대표하는 묶음 크기가 2배가 된다. 배열 하나로 구현하면 단계마다 묶음 크기(1, 2, 4, 8, …)를 들고 다니며 묶음 단위로 비교·교환한다.
• 큰 원소를 재귀 정렬할 때 짝인 b가 함께 따라 움직여야 한다. 인덱스나 묶음 단위 이동으로 쌍 관계를 유지한다.
• n이 홀수일 때 남는 원소는 짝이 없는 b로 취급해 마지막 묶음에 넣는다. 이 원소는 범위 제한이 없으니 주 사슬 전체에서 탐색한다.
• 비교 횟수 대신 실행 시간이 중요하다면 이 정렬은 쓰지 않는다. 삽입 때마다 원소를 밀어야 하므로 배열 기반 구현은 O(n²) 이동이 든다.

정리

• Ford-Johnson은 비교 횟수 최소화가 목표인 정렬이다. 정보 이론 하한에 매우 가깝다.
• 쌍 비교 → 큰 원소 재귀 정렬 → 작은 원소 이진 삽입의 3단계다.
• 삽입 순서를 야콥스탈 수로 묶어, 모든 이진 탐색이 2ᵏ − 1 범위 안에서 끝나게 한다.
• 실전 정렬로는 느리다. 비교가 비쌀 때나 비교 횟수를 따지는 문제에서 쓴다.

관련 노트: 기본 정렬(삽입 정렬), 병합 정렬과 퀵 정렬, 이분 탐색, 선형 점화식의 일반항