최근, TimSort 라는 정렬 알고리즘 이 화제가 되었습니다. TimSort 는 빠르고 안정적인 정렬 알고리즘으로, Python(>=2.3) 과 Java SE 7, 그리고 Android 에서 표준 정렬 알고리즘으로 채용되었다고 합니다.
C++ 의 std::sort() 보다도 빠르다는 벤치마크 결과가 화제가 되어(나중에 벤치마크의 오류라고 판명났지만), 그때 TimSort 의 존재를 알았습니다. 실제로 랜덤 데이터에 대해서는 Quick Sort(IntroSort) 보다 빠르지는 않지만, 정렬이라는 단순한 일을 하는 알고리즘 이 지금도 더욱 개량해오며 사람들의 관심을 끌고 있다는 것은 흥미깊은 일입니다.
개요
TimSort 는 한마디로 하면, “STL 의 IntroSort 의 Merge Sort 버젼” 입니다. 조금 더 정확하게 이야기하면 거기에 몇가지의 Heuristic 이라고 할 수 있습니다. 몇가지 테크닉의 집합체이기에, 이런 것들을 어디까지 TimSort 라고 불러야 할지는 모르겠습니다.
IntroSort
IntroSort 란, Quick Sort 의 개량버젼입니다. Quick Sort 는 상당히 빠른 알고리즘이지만, 몇가지 약점이 있습니다.
약점 중 하나는 최악계산량입니다. 피벗(Pivot)의 선택이 잘 이뤄지지 않으면, 요소 수의 2제곱에 비례한 시간이 걸리게 됩니다. 몇가지 요소를 샘플링한 뒤에 중앙값을 Pivot하면, 평균적인 데이터에 대해서는 꽤 양호한 성능을 바타내지만, 그것은 최악계산량을 보증하는 것은 아닙니다. 예를 들어, 특정 구현에 대해서 2 제곱의 시간이 걸리는 데이터를 만드는 것은 쉽고, 그것을 노려서 공격하는 것도 가능합니다.
IntroSort 에서는 이에 대처하기 위해, 재귀탐색이 요소수의 대수를 넘으면 HeapSort 로 바꾸게 됩니다. 이에 의해 최악계산량을 O(n log n)에 대입하고, 평균적인 데이터에서는 QuickSort 에 필적하는 성능을 달성합니다.
다른 하나의 약점은 요소 수가 적은 경우입니다. 적은 요소 수(< 32 정도) 에서는 계산량의 순서가 커도 단순히 오버헤드가 적은 Insert Sort 나 Select Sort 같은 알고리즘이 더 빠릅니다. 그리고 분할이 진행된 요소수가 줄어들면, Insert Sort 로 바뀝니다.
TimSort
Merge Sort 는 최악계산량 O(n log n) 이 안정적인 정렬 알고리즘으로, Quick Sort 같은 최악계산량의 문제는 발생하지 않습니다. 그러나, 요소수가 적은 경우는 오버헤드에 의해 Quick Sort 와 마찬가지로 느려집니다. TimSort는 일반적인 Merge Sort 와는 달리, 미리 어느 정도의 크기의 정렬이 끝난 열(run 이라고 부릅니다) 로 분할하고 병합합니다.
run 크기의 결정
run 크기는 Insert Sort 가 가장 빠른 범위(< 32) 가 되도록 크게 합니다.또, run 의 갯수가 2의 거듭제곱일 때, 뒷단의 병합이 빨리 끝나기 때문에 [16, 32] 의 범위로, run 의 갯수가 2의 거듭제곱이 되는 것을 선택합니다.
run 으로의 분할
우선 처음으로, 입력열의 작은 정렬이 끝난 열로 분해합니다. 입력열을 앞에서 순서대로 놓고, 단순증가하고 있는 최대의 접두사를 요구합니다. 그것이 어느 정도 커지면 그것을 하나의 run 이라고 합니다. 증가열의 크기가 너무 작은 경우는, Insert Sort 를 사용해 확장합니다. 이 때에 사용하는 Insert Sort 는 전방의 요소가 정렬이 끝났기 때문에, 도중에 수행할 수 있습니다.
처음의 두 요소가 내림차순이 되었을 경우, 증가열에서는 되도록 감소열을 위해 반전합니다. 이에 의해 Insert Sort 의 횟수를 줄일 수 있습니다. 여기에서 주의할 것은, 안전성을 위해서 감소열은 strict(<) 이어야 합니다.
입력열의 정렬이 끝난 후, 이 상태로 한번 데이터를 훑어 보는 것만으로 정렬이 끝납니다. 이 때문에 속도가 빠른 것입니다.
2분할 Insert Sort
TimSort 에서는 단순한 Insert Sort 가 아닌, 2분할 Insert Sorrt 가 사용됩니다. 이것은 요소의 삽입위치의 결정을 위해서, 정렬이 끝난 부분을 2분할 탐색하는 것입니다. 안전성을 가지도록 삽입위치를 정할 필요가 있다는 것에 주의해야 합니다.
Merge
어느 정도의 사이즈의 run 이 만들어졌다면, 이것을 병합(Merge)합니다. 병합은 평상시대로 2개씩 병합합니다. 이것을 효율있게 수행하기 위해서, 스택을 사용해 run 을 관리합니다. 앞의 상황에서 작성된 run 은 우선 스택에 올려지고, 다음과 같은 불변상황을 만족하도록 병합됩니다.
- length[top] + length[top -1] < length[top -2]
- length[top] < length[top -1]
이것을 만족하는 스택의 깊이는 가장 큰 것이라도 요소 수의 대수가 됩니다. 또, 작은 것 끼리 병합되기에, 계산량 O(n log n)을 보증할 수 있습니다 (TimSort 의 경우는 거의 대부분 같은 크기의 run 이 병합되기에 실용적으로도 충분히 빠르다고 말할 수 있습니다).
2개의 run 의 병합
TimSort 에서는 2개의 run 의 병합에도 많이 고려되어 있습니다.
연속영역
TimSort 에서는 반드시 마주 보고 있는 메모리 영역을 병합합니다. 이것은 앞의 스택의 불변조건에 의해 run의 병합을 수행하면 자연스레 만족됩니다. 옆에 있는 메모리의 영역을 병합하면
* 앞 줄 중 뒷 줄의 선두보다 적은 것
* 뒷 줄의 뒤의 요소 중, 앞 줄의 맨 뒤의 요소보다 큰 것
의 복사를 생략할 수 있습니다. 연속한 영역의 부분열만 병합하면 되는 것입니다.
범위없는 2분할 탐색
생략하는 요소를 계산하기 위해서도 2분할 탐색을 이용합니다. 단, 일반적인 2분할 탐색과는 달리, 맨 처음 범위를 고정하지 않고, 다음의 두 단계로 탐색을 수행합니다.
* 1, 2, 4, 8, ... 처럼 2의 거듭제곱 순서의 요소를, 요소가 커질때까지 본다
* 원하는 요소가 어느 범위에 있는 지 요구하기 때문에 (예를 들어, 8번째의 요소가 큰 것이라면, \[4,8\] 에 원하는 요소가 있습니다) 다시 그 범위로 2분할 탐색
병합에 있어서는, 원하는 요소는 꽤 앞에 있을 것이기에, 일반적인 2분할 탐색보다 비교횟수는 적을 것입니다( 평균적인 데이터에 대해서는 선형검색이 빠르다고 생각합니다)
Galloping Mode
남은 부분의 병합은 평상시대로, 맨 앞의 요소를 비교해서 병합해나가지만, 같은 열에서 연속해서 많이 채용되기 시작하면 (>=7), 갤로핑 모드(Galloping Mode)라고 불리는 모드로 들어갑니다.
갤로핑 모드란, 한쪽의 맨 앞의 요소보다도 작은 요소가 다른 쪽의 맨앞에 몇개 있는지를 위의 범위없는 2분할 탐색으로 구하는 것입니다. 같은 줄에서 어느정도 이상의 연속한 경우, 더 많이 연속한다고 예상할 수 있기에, 이것이 제대로 작동할 것입니다.
Conclusion
이상이 TimSort 의 알고리즘입니다. 실질적으로는 Merge Sort 라고 할 수 있습니다. 랜덤한 데이터에 대해서는 IntroSort 나 C++ 의 std::stable_sort() 와 비교해서 속도에 우위성이 있지는 않지만(std::stable_sort() 도 Merge Sort + 작은 요소로 Insert Sort), 정렬이 끝난 데이터, 또는 거의 정렬이 끝난 데이터에 대해서는 맨 처음의 run 작성 및 갤로핑 모드에서 큰 폭의 생략이 예상되기 때문에, 실제 데이터에 그런 경향이 있다면 좋은 성능을 얻을 수 있습니다. 또, Quick Sort 처럼 최악계산량이 문제가 되는 일이 없기 때문에, 이것을 표준으로 채용하는 것은 보안상의 관점에서도 충분히 메리트가 있다고 할 수 있습니다.