이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.
목표: 배열을 낮은 순서에서 높은 순서로(또는 높은 순서에서 낮은 순서로) 정렬한다.
1945년 John von Neumann이 발명한 병합 정렬은 최선, 최악, 평균 시간 복잡도가 모두 **O(n log n)**인 효율적인 알고리즘이다.
병합 정렬 알고리즘은 분할 정복 방식을 사용한다. 큰 문제를 작은 문제로 나누고 해결하는 방식이다. 병합 정렬 알고리즘을 먼저 분할하고 나중에 병합하는 과정으로 이해하면 된다.
n개의 숫자를 올바른 순서로 정렬해야 한다고 가정해 보자. 병합 정렬 알고리즘은 다음과 같이 동작한다:
숫자 배열 [2, 1, 5, 4, 9]가 주어졌다고 가정한다. 이 배열은 정렬되지 않은 상태다. 이 배열을 더 이상 나눌 수 없을 때까지 계속 분할하는 것이 목표다.
먼저, 배열을 두 부분으로 나눈다: [2, 1]과 [5, 4, 9]. 이들을 계속 나눌 수 있는가? 가능하다!
왼쪽 부분에 집중한다. [2, 1]을 [2]와 [1]로 나눈다. 이들을 더 나눌 수 있는가? 불가능하다. 이제 다른 부분을 확인한다.
[5, 4, 9]를 [5]와 [4, 9]로 나눈다. 당연히 [5]는 더 이상 나눌 수 없지만, [4, 9]는 [4]와 [9]로 나눌 수 있다.
분할 과정은 다음과 같은 결과로 끝난다: [2] [1] [5] [4] [9]. 각 부분이 단 하나의 요소로만 구성된 것을 확인할 수 있다.
배열을 분할한 후, 이제 정렬하면서 각각의 덩어리를 병합해야 한다. 큰 문제를 해결하는 대신 여러 작은 문제를 해결한다는 아이디어를 기억하자. 각 병합 단계에서는 한 덩어리를 다른 덩어리와 병합하는 데 집중한다.
예를 들어, 덩어리 [2], [1], [5], [4], [9]가 주어졌을 때, 첫 번째 단계에서는 [1, 2], [4, 5], [9]로 병합된다. [9]는 홀수 개로 남아 이번 단계에서 병합할 수 없다.
다음 단계에서는 [1, 2]와 [4, 5]를 병합한다. 결과는 [1, 2, 4, 5]가 되며, [9]는 여전히 홀수 개로 남는다.
마지막으로, 두 덩어리 [1, 2, 4, 5]와 [9]가 병합되며, 최종적으로 정렬된 배열 [1, 2, 4, 5, 9]를 얻게 된다.
Swift에서 머지 정렬은 다음과 같이 구현할 수 있다:
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}코드가 동작하는 방식을 단계별로 설명하면 다음과 같다:
배열이 비어 있거나 단일 요소만 포함하면 더 작은 조각으로 나눌 수 없다. 배열을 그대로 반환한다.
중간 인덱스를 찾는다.
이전 단계에서 찾은 중간 인덱스를 사용해 배열의 왼쪽 부분을 재귀적으로 나눈다.
배열의 오른쪽 부분도 재귀적으로 나눈다.
마지막으로 모든 값을 병합하며 항상 정렬된 상태를 유지한다.
병합 알고리즘은 다음과 같다:
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
orderedPile.reserveCapacity(leftPile.count + rightPile.count)
// 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}이 메서드는 복잡해 보이지만 실제로는 매우 직관적이다:
두 배열을 병합할 때 진행 상황을 추적하기 위해 두 개의 인덱스가 필요하다.
병합된 배열이다. 현재는 비어 있지만, 이후 단계에서 다른 배열의 요소를 추가하며 채워나간다. 이 배열에 최종적으로 들어갈 요소의 수를 미리 알고 있으므로, 나중에 재할당 오버헤드를 피하기 위해 용량을 미리 확보한다.
이 while 루프는 왼쪽과 오른쪽 배열의 요소를 비교하며 orderedPile에 추가한다. 결과가 항상 정렬된 상태를 유지하도록 한다.
이전 while 루프에서 빠져나오면 leftPile 또는 rightPile 중 하나의 내용이 완전히 orderedPile에 병합된 상태다. 이 시점에서는 더 이상 비교할 필요가 없다. 남은 배열의 내용을 그대로 추가하면 된다.
merge()가 어떻게 동작하는지 예를 들어보자. leftPile = [1, 7, 8]과 rightPile = [3, 6, 9]가 있다고 가정한다. 각각의 배열은 이미 정렬된 상태다. 이 두 배열을 병합해 하나의 큰 정렬된 배열로 만드는 과정은 다음과 같다:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r
왼쪽 인덱스 l은 왼쪽 배열의 첫 번째 요소인 1을 가리킨다. 오른쪽 인덱스 r은 3을 가리킨다. 따라서 orderedPile에 추가할 첫 번째 요소는 1이다. 그런 다음 왼쪽 인덱스 l을 다음 요소로 이동한다.
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
-->l r
이제 l은 7을 가리키고 r은 여전히 3을 가리킨다. 가장 작은 요소를 orderedPile에 추가하므로 3을 추가한다. 상황은 다음과 같다:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r
이 과정이 반복된다. 각 단계에서 leftPile 또는 rightPile에서 가장 작은 요소를 선택해 orderedPile에 추가한다:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r
이제 왼쪽 배열에는 더 이상 요소가 없다. 오른쪽 배열에 남은 요소를 그대로 추가하면 병합이 완료된다. 최종 병합된 배열은 [ 1, 3, 6, 7, 8, 9 ]이다.
이 알고리즘은 매우 간단하다. 두 배열을 왼쪽에서 오른쪽으로 이동하며 각 단계에서 가장 작은 요소를 선택한다. 각 배열이 이미 정렬된 상태라는 보장이 있기 때문에 이 방법이 동작한다.
지금까지 본 병합 정렬 알고리즘은 '상향식' 접근 방식이다. 배열을 작은 단위로 나눈 후 병합하는 방식이다. 하지만 배열을 정렬할 때는 (연결 리스트와 달리) 나누는 단계를 건너뛰고 바로 개별 배열 요소를 병합할 수 있다. 이를 '하향식' 접근 방식이라 한다.
이제 조금 더 깊이 들어가 보자. :-) 다음은 Swift로 구현한 완전한 하향식 병합 정렬이다:
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let n = a.count
var z = [a, a] // 1
var d = 0
var width = 1
while width < n { // 2
var i = 0
while i < n { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}상향식 버전보다 복잡해 보이지만, 주요 부분은 merge() 함수의 세 개의 while 루프와 동일하다.
주요 포인트:
병합 정렬 알고리즘은 임시 작업 배열이 필요하다. 왼쪽과 오른쪽 부분을 병합하면서 동시에 내용을 덮어쓸 수 없기 때문이다. 매번 새로운 배열을 할당하는 것은 비효율적이므로, 두 개의 작업 배열을 사용하고 d 값(0 또는 1)을 통해 전환한다. z[d] 배열은 읽기용이고, z[1 - d] 배열은 쓰기용이다. 이를 더블 버퍼링이라 한다.
개념적으로 하향식 버전은 상향식 버전과 동일하게 작동한다. 먼저 한 요소씩 작은 단위를 병합하고, 두 요소씩, 네 요소씩 점점 큰 단위를 병합한다. 단위의 크기는 width로 결정된다. 초기값은 1이지만, 각 루프 반복 후 두 배로 증가한다. 이 외부 루프는 병합할 단위의 크기를 결정하며, 병합할 부분 배열이 점점 커진다.
내부 루프는 각 단위를 순회하며 두 부분을 병합해 더 큰 단위로 만든다. 결과는 z[1 - d] 배열에 기록된다.
이 부분은 상향식 버전과 동일한 로직이다. 주요 차이점은 더블 버퍼링을 사용한다는 점이다. 값은 z[d]에서 읽고 z[1 - d]에 기록된다. 또한 요소를 비교하기 위해 < 대신 isOrderedBefore 함수를 사용하므로, 이 병합 정렬 알고리즘은 제네릭하다. 원하는 어떤 타입의 객체도 정렬할 수 있다.
이 시점에서 z[d] 배열의 width 크기 단위가 z[1 - d] 배열의 width * 2 크기 단위로 병합되었다. 여기서 활성 배열을 전환해 다음 단계에서 방금 생성한 새로운 단위를 읽는다.
이 함수는 제네릭하므로, 요소를 비교할 적절한 isOrderedBefore 클로저를 제공하면 어떤 타입도 정렬할 수 있다.
사용 예시:
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]병합 정렬 알고리즘의 속도는 정렬해야 하는 배열의 크기에 따라 달라진다. 배열이 클수록 더 많은 작업을 수행해야 한다.
초기 배열이 이미 정렬되어 있는지 여부는 병합 정렬 알고리즘의 속도에 영향을 미치지 않는다. 요소의 초기 순서와 관계없이 동일한 양의 분할과 비교 작업을 수행하기 때문이다.
따라서 최선, 최악, 평균 경우의 시간 복잡도는 항상 **O(n log n)**이다.
병합 정렬 알고리즘의 단점은 정렬 중인 배열과 동일한 크기의 임시 "작업" 배열이 필요하다는 점이다. 퀵 정렬과 달리 제자리 정렬이 아니다.
대부분의 병합 정렬 알고리즘 구현은 안정적인 정렬을 제공한다. 이는 동일한 정렬 키를 가진 배열 요소들이 정렬 후에도 서로 상대적인 순서를 유지한다는 의미다. 숫자나 문자열 같은 단순한 값에는 중요하지 않지만, 더 복잡한 객체를 정렬할 때는 문제가 될 수 있다.
Kelvin Lau가 작성. Matthijs Hollemans가 추가 내용 작성.