파이썬의 정렬(Timsort)

정렬이라는 주제는 처음 프로그래밍을 배울 때 간단한 정렬을 구현해보는 것으로 접하기 시작하여, 자료구조론, 알고리즘론을 통하여 다양한 정렬 알고리즘의 시간 복잡도와 동작 원리에 대해서 배우게 된다.

"그렇다면 내가 사용하고 있는 프로그래밍 언어에는 정렬이 어떻게 구현되어 있을까?"라는 의문으로 시작된 이 글은 새로운 정렬이 탄생하게 된 배경과 Tim sort의 동작 원리 및 최적화 알고리즘을 소개한다.

새로운 정렬의 필요성

다음은 잘 알려진 비교 정렬 알고리즘들을 비교하여 정리한 표이다.

흔히 Bubble sort, Insertion sort는 평균 시간 복잡도 $O(n^2)$으로 느린 정렬 알고리즘, Merge sort, Heap sort, Quick sort는 평균 $*O(nlogn)*$으로 빠른 알고리즘으로 알려져 있다.

정렬의 성능을 파악하는 지표에 시간은 필수이므로 Merge sort, Heap sort, Quick sort를 사용하는 것이 좋을 것 같다.

이 세 개의 정렬 알고리즘 중 어떤 것을 표준 정렬 알고리즘으로 선정하는 것이 좋을까?

최선의 경우 $*O(n)*$, 최악의 경우$*O(nlogn)*$에 추가 메모리도 들지 않는 Heap sort가 제일 성능이 좋은 알고리즘이 아닐까 하는 생각이 들 수도 있지만 평균 시간 복잡도가 $*O(nlogn)*$이라는 의미를 좀 더 자세히 살펴볼 필요가 있다.

시간 복잡도가 $*O(nlogn)*$이라는 말은 실제 동작 시간은 $C × n\log{}n + α$라는 의미이다.

상대적으로 무시할 수 있는 부분인 $α$ 부분을 제하면 $*nlogn*$에는 앞에 $*C*$라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생긴다.

이 $C$라는 값에 큰 영향을 끼치는 요소로 '알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'가 있다.

참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다.

쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다.

메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.

참조 지역성 원리의 개념과 함께 다시 한 번 세 정렬 알고리즘을 비교해보겠다.

Heap sort

Heap sort의 경우 대표적으로 참조 지역성이 좋지 않은 정렬이다. 위의 이미지에서 확인할 수 있듯이 한 위치에 있는 요소를 해당 요소의 인덱스 두 배 또는 절반인 요소와 반복적으로 비교하기에 캐시 메모리에서는 예측하기가 매우 어렵다. 그렇기에 $*C*$는 상대적으로 다른 두 정렬들보다 큰 값으로 정의된다.

Merge sort

이와 달리, Merge sort의 경우 인접한 덩어리를 병합하기에 참조 지역성의 원리를 어느 정도 잘 만족한다. 그러나 입력 배열 크기만큼의 메모리를 추가로 사용한다는 단점이 있다.

Quick sort

Quick sort의 경우 pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기에 참조 지역성이 좋으며 메모리를 추가로 사용하지 않는다.

실제로도 $*C*$의 값은 다른 두 정렬들보다 작은 값으로 정의되어 있고 평균 시간 복잡도는 셋 중에 가장 빠르다고 알려져 있다.

그러나 pivot을 선정하는 방법에 따라 최악의 경우 $O(n^2)$이 될 수 있다는 단점이 있다.

위와 같이 모든 정렬 알고리즘에는 장단점이 있어 어떤 한 정렬이 탁월하게 좋다고 선택할 수가 없었다.

상수 $C$의 값이 너무 커지지 않게 동작하며, 추가 메모리도 많이 사용하지 않고, 최악의 경우에도 $*O(nlogn)*$으로 동작하는 정렬 알고리즘이 필요했다.

Tim sort의 등장

2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort가 등장했다.

이 정렬 알고리즘은 Insertion sort와 Merge sort를 결합하여 만든 정렬이다.

실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 $*O(n)*$, 평균은 $*O(nlogn)*$, 최악의 경우 시간 복잡도는 $*O(nlogn)*$이다.

Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 $*O(nlogn)*$ 정렬 알고리즘의 단점을 최대한 극복한 알고리즘이다.

현재 2.3 이후 버전의 Python, Java SE 7, Android, Google chrome (V8), 그리고 swift까지 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있다.

Tim sort의 기본 원리

Tim sort 알고리즘은 Insertion sort와 Merge sort를 결합한 알고리즘이다.

여기에 시간 복잡도 $*O(n2)*$으로 알려져 있는 Insertion sort를 왜 결합했을까?

Insertion sort

Insertion sort는 위와 같은 방법으로 동작한다.

인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하고 있는 것을 확인할 수 있다.

이에 따라 Insertion sort의 상수 $*C*$를 $C_i$, $O(n\log{}n)$ 정렬 알고리즘 중 $*C*$ 값이 가장 작다고 알려져 있는 Quick sort의 상수 $*C*$를 $C_q$라 할 때, 작은 $*n*$에 대하여 $C_i × n^2 \lt C_q × n\log{}n$이 성립한다.

즉, 작은 $*n*$에 대하여 Insertion sort가 빠르다는 것이다.

이것을 이용하여 전체를 작은 덩어리로 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.

$2^x$개씩 잘라 각각을 Insertion sort로 정렬하면 일반적인 Merge sort보다 덩어리별 $x$개의 병합 동작이 생략되어, Merge sort의 동작 시간을 $C_m × n\log{}n$이라 할 때 Tim sort의 동작 시간은 $C_m × n(\log{}n - x) + α$가 된다.

이때의 $*x*$ 값을 최대한 크게 하고 $*α*$ 값을 최대한 줄이기 위해 여러 가지 최적화 기법이 사용된다.

Tim sort의 최적화 기법

Run

$*α*$를 유지하면서 $*x*$를 크게 하는 방법에는 무엇이 있을까? 

$2^x$개씩 잘라 각각을 Insertion sort로 정렬하되, 이후는 Insertion sort를 진행하지 않고 덩어리를 최대한 크게 만들어 병합 횟수를 최대한 줄이는 것이다.

위 그림의 배열을 $2^2$개씩 덩어리로 자른다고 가정한다.

맨 앞의 두 원소가 $[10,13]$으로 증가하고 있으므로 이 덩어리는 증가하는 원소가 담긴 덩어리이다.

덩어리가 $2^2$가 될 때까지 뒤의 원소에 대해 Insertion sort를 진행한다. 

$9$와 $15$가 순차적으로 이 덩어리에 삽입되고 $[9,10,13,15]$로 정렬된다.

여기서 멈추지 않고 최대한 덩어리를 크게 만들기 위하여, 뒤의 원소 또한 증가한다면 이 덩어리에 포함시킨다.

이 배열에서 $[18,21]$의 경우 이어지는 증가하는 원소들이므로 같은 덩어리로 묶는다.

이때는 Insertion sort를 사용하지 않고 앞 원소와의 대소만 비교하면 된다. 

$13$부터는 새로운 덩어리로 만든다. 덩어리의 첫 두 원소가 $[13,8]$으로 감소하고 있으므로 이 덩어리는 감소하는 방향으로 정렬을 진행한다.

앞 네 개의 원소가 $[13,11,8,5]$로 정렬되며 뒤의 $[3]$ 또한 감소하기에 같은 덩어리에 포함될 수 있다는 것을 알 수 있다.

이와 같이 덩어리의 첫 두 원소의 대소 관계로 이 덩어리를 증가하는 덩어리, 감소하는 덩어리로 정의하여 $2^x$개까지는 Insertion sort를 진행하고 그 이후의 원소에 대해서 가능한 한 크게 덩어리를 만든다.

이런 덩어리를 run이라고 부르며 이때의 $2^x$를 minrun이라 칭한다.

완전한 무작위가 아닌 실생활의 데이터의 특성상 증가하거나 감소하는 부분이 많을 것이고 이 원소를 한 번에 묶기 위한 작업이다.

이미 정렬된 배열에서는 하나의 run만 생성되기에 Tim sort의 최선의 시간 복잡도가 $O(n)$이 되는 것이다.

증가하는 run과 감소하는 run은 다음과 같이 정의한다.

• 증가하는 run: $*a0≤a1≤a2≤a3≤...*$
• 감소하는 run: $*a0>a1>a2>a3>...*$

이후 감소하는 run은 뒤집어서 모든 run이 증가하는 run이 되도록 변환한다.

위의 수식에서 감소하는 run의 부등호에 등호가 없는 이유, 즉 값이 동일한 원소에 대하여 다루지 않는 이유는, Tim sort는 안정적인 정렬이기에 뒤집을 경우 동일한 원소의 순서가 뒤바뀌기 때문이다.

Tim sort의 경우 전체 원소의 개수를 $N$이라 할 때, minrun의 크기를 $min(N, 2^5 ∼ 2^6)$로 정의한다.

고정된 수로 정의하지 않는 이유는 더 느려지는 경우도 있기 때문이다.

예를 들어 $*N*$은 $1088$, minrun은 $32$일 경우 전체 run의 개수는 최대 $1088/32=34=2^5+2$가 된다.

이 경우 $2$개씩 병합하는 Merge sort의 특성상 $2$의 거듭제곱이 아니기에 minrun이 $34$이고 run의 개수가 $32=2^5$인 경우보다 더 많은 시간이 걸린다.

따라서 Tim sort에서는 run의 개수가 $2$의 거듭제곱이 되도록 유동적으로 minrun 값을 정하여 사용한다.

Binary Insertion sort

Tim sort에서 사용하는 Insertion sort는 Binary Insertion sort이다.

Binary라는 용어에서 알 수 있듯이, 삽입해야 할 위치를 찾을 때까지 비교하는 대신, 앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색을 진행하여 위치를 찾는다.

이분 탐색은 참조 지역성은 떨어지지만 한 원소를 삽입할 때 $O(n)$번의 비교를 진행하는 대신 $O(\log{}n)$번의 비교를 진행하기에 작은 $n$에 대하여 좀 더 시간을 절약할 수 있다.

삽입해야 할 위치를 빠르게 찾아도 그 위치에 삽입하는 과정은 $O(n)$이기에 전체의 시간 복잡도는 $O(n^2)$으로 일반적인 Insertion sort와 동일하지만 그 위치에 삽입하고 나머지 원소를 시프트하는 연산은 빠르기 때문에 훨씬 효율적이다.

Merge

배열을 맨 앞 원소부터 훑으며 run의 크기가 minrun보다 작을 경우 Binary Insertion sort를 진행하고 증가하는 run인지, 감소하는 run인지에 따라 조건에 맞게 최대한 run의 크기를 키우고, 감소하는 run의 경우 뒤집어서 하나의 증가하는 run을 생성했다 우리는 이제 효율적인 방법으로 run들을 병합할 차례이다.

다음 그림은 Merge sort의 동작 원리를 보여준다.

Merge sort 동작 원리(원본 출처: Merge sort - Wikipedia)

두 덩어리를 병합하여 정렬된 하나의 덩어리로 만드는 과정에서 $n$의 추가 메모리와 두 덩어리의 크기의 합만큼의 시간이 소요된다는 것을 확인할 수 있다.

그리고 안정성을 유지하기 위하여 인접한 덩어리에 대하여 병합을 진행했으며, 그 중에서도 비슷한 크기의 덩어리와 병합하여 효율성을 증대시킨 것을 알 수 있다.

그러나 Tim sort에서는 각각의 run의 길이가 제각각이므로 Merge sort와 같은 방법으로 진행하기에는 어려움이 있다.

어떻게 하면 비슷한 크기의 덩어리끼리 병합하도록 구현할 수 있을까?

Tim sort에서는 하나의 run이 만들어질 때마다 스택에 담아 효율적으로 병합을 진행한다.

이때 run을 스택에 push할 때마다 스택의 맨 위의 세 run이 위의 그림과 같이 두 조건을 만족해야 한다.

위의 그림과 같이 두 조건을 만족하지 않는 상황이 되면 $*B*$는 $*A*$와 $*C*$ 중 작은 run과 병합된다.

병합한 후에도 스택의 맨 위 세 개의 run이 조건을 만족하지 않으면 조건을 만족할 때까지 병합을 진행한다.

위 오른쪽 그림도 1번 조건을 만족하지 않으므로 이후 추가로 병합이 진행될 것이다.

규칙은 이렇다. 과연 이런 식으로 진행하면 효율적으로 병합할 수 있는 것일까?

스택에 두 조건을 만족하게 쌓아 올릴 경우 어떤 장점이 있을까?

두 조건을 만족하는 스택을 그려보면 위의 그림과 같다.

첫 번째 장점은 스택에 들어있는 run의 수를 작게 유지할 수 있다는 것이다.

1번 조건인 $|C| \gt |A| + |B|$는 스택의 맨 위의 원소를 $stack[0]$으로 하여 번호를 매기면 $stack[2] \gt stack[0] + stack[1]$이라 할 수 있다.

원소를 추가할 때에도 이 조건에 맞게 유지를 하니 결국 스택에 있는 모든 run은 $2$보다 같거나 큰 $i$에 대해 $stack[i] \gt stack[i-1] + stack[i-2]$를 만족한다.

이는 피보나치 수열과 유사하다.

각 run의 길이는 최소 피보나치 수보다 크므로 $*n*$이 1억일 때에도 스택의 크기는 40보다 작게 유지된다.

두 번째 장점은 비슷한 크기의 덩어리와 병합할 수 있다는 것이다.

조건을 만족하지 않을 경우 BB는 AA와 CC 중 작은 run과 병합한다고 했는데 이는 $*B*$에서 인접한 두 run을 모두 확인하여 그 중 가장 비슷한 run과 병합한다는 것이다.

최소한의 메모리를 이용하여 최고의 효율을 내기 위한 방법이다.

2 Run Merge

가장 효율적인 방법으로 병합할 두 run을 알아냈으니 이 두 run을 Merge sort와는 다른 효율적인 방법으로 병합해보자.

Merge sort의 가장 큰 단점이었던 추가 메모리를 $n$ 사용한다는 점 또한 극복해야 할 문제이다.

위의 그림은 이웃한 초록색 run $A$와 빨간색 run $B$을 하나의 run으로 병합하는 과정을 보여준다.

먼저 병합하기 전 두 개의 run 중 크기가 더 작은 run인 $*A*$를 복사한다.

이후 각 run의 시작 부분부터 크기 비교를 하여 작은 순서대로 앞을 채우면서 병합을 진행한다.

run $B$의 원소가 병합될 때마다 화살표 또한 한 칸씩 앞으로 전진하므로 아직 병합되지 않은 run $B$의 원소의 위치에 다른 수가 적힐 일이 존재하지 않는다는 것을 알 수 있다.

run $*B*$의 크기가 더 작을 경우에는 이와 반대로 진행이 된다. 

$*B*$를 복사한 뒤, 각 run의 끝 부분부터 크기 비교를 하여 큰 순서대로 뒤를 채우면서 진행한다.

두 경우 모두 같은 수인 $13$을 비교할 때, 안정적인 정렬을 고려하여 병합한 부분도 확인할 수 있다.

이와 같이 두 run 중 크기가 작은 run을 담을 메모리가 필요하기에 병합을 진행할 때 최악의 경우 $n/2$의 추가 메모리를 사용하는 것을 알 수 있다.

비록 Merge sort와 같은 $O(n)$의 추가 메모리를 사용하지만 절반을 절약할 수 있는 것이다.

여기서 위의 그림과 같이 한 번 더 최적화를 진행한다.

run $A$, $B$를 병합하기 전, 병합을 수행할 필요가 없는 구간을 먼저 계산한다.

run $*A*$의 맨 앞 원소 $[3,5,8]$은 run $*B*$의 맨 앞 원소인 $9$보다 작기 때문에 병합을 수행하지 않고 현재 위치에 있어도 문제가 되지 않는다.

같은 방법으로 run $B$의 맨 뒤 원소 $[13,15,18,21]$은 run $A$의 맨 뒤 원소인 $13$보다 같거나 크기 때문에 이 원소들 또한 병합을 수행할 필요가 없는 구간이다.

이제 $[11,13], [9,10]$ 이렇게 두 부분 run만 병합을 진행하면 되기에 단 $4$번의 비교와 단 $2$개의 추가 메모리만으로 병합을 효율적으로 진행할 수 있다.

이 필요 없는 구간을 계산하는 과정을 이분 탐색으로 진행할 경우, run의 길이를 $k$라 할 때 $O(\log{}k)$의 시간이 소요된다.

이만큼의 추가 시간을 소요하고 더 빠르게 계산이 되면 좋겠지만, 필요 없는 구간이 없을 수도 있기에 오히려 더 늦춰질 수도 있는 최적화 방법이다.

그럼에도 불구하고 실생활 데이터에서 많은 시간을 절약할 수 있기에 Tim sort에서는 이분 탐색을 이용한 최적화 방법을 도입하고 있다.

Galloping

마지막으로, 병합하는 과정에 추가로 사용되는 Galloping이라는 최적화 방법을 간단히 설명하겠다.

위에서는 두 run $A$, $B$를 병합할 때 화살표가 가리키고 있는 두 원소를 대소 비교하여 병합을 진행했다.

여기에 '한 run을 계속해서 참조할 경우가 많지 않을까?'라는 무작위적이지 않은 실생활 데이터의 특성을 이용하여 Galloping mode(질주 모드)일 경우 하나의 run을 빠르게 참조하도록 동작한다.

위는 이웃한 두 run을 병합하는 과정 중 일부를 잘라 표현한 그림이다.

초록색으로 색칠되어 있는 부분은 run $A$의 일부, 빨간색으로 색칠되어 있는 부분은 run $*B*$의 일부이다.

처음에는 화살표가 가리키고 있는 두 원소를 대소 비교를 하여 어느 run의 원소를 넣을지 정한다.

이 때의 방법을 One pair at a time mode라 칭한다.

이때 run $B$의 원소가 $3$번 연속으로 병합되었기에 Galloping mode로 전환된다.

이 모드에서는 $1, 2, 4, 8, ...$과 같이 $2^k$로 뛰어 넘으며 대소 비교를 진행한다.

위의 그림에서는 $10, 30, 75$와 비교하는 것을 알 수 있다. 

$75$와 비교하면 $70 \lt 75$이므로 $[45,50,60,75]$의 범위에서 이분 탐색을 진행하여 어느 위치까지 병합할지 결정한다.

이후 다시 하나의 run에서 연속적으로 병합되지 않을 경우 One pair at a time mode로 돌아가 다시 하나씩 비교를 진행한다.

실제 코드에서는 MIN_GALLOP번 연속으로 한 run에서 병합되었을 경우 Galloping mode로 전환하며 MIN_GALLOP는 전체 배열을 정렬하는 과정에서 Galloping mode에 들어가는 횟수가 많았다면 감소하고 아니라면 증가하여 좀 더 효율적으로 동작하도록 진행한다.

마치며

Tim sort는 Merge sort를 기반으로 하되, 좀 더 효율적으로 run을 나누고 제각기 다른 크기를 가진 run을 최대한 효율적인 방법으로 병합하며 실생활 데이터의 특성을 이용하여 여러 가지 최적화 기법을 도입한 정렬 알고리즘이다.

완전히 무작위인 데이터에 대해서는 속도가 빠른 편은 아니지만 일정한 패턴이 있는 일반적인 데이터에 대해서는 빠른 성능을 보여주고 안정적이며 최악의 시간 복잡도가 $O(n\log{}n)$이기에 지금까지도 많은 언어에서 표준 정렬 알고리즘으로 채택하여 사용하고 있다.

지금까지 새로운 정렬이 탄생하게 된 배경과 Tim sort의 동작 원리 및 최적화 알고리즘에 대해 알아보았다.

직접 정렬을 구현해야 할 일은 드물지만 자료구조론과 알고리즘론에서 배웠던 개념을 응용하여 이해해볼 만한 여러 가지 최적화 기법이 들어있었다.

추후 기회가 된다면 다른 알고리즘으로 다시 찾아오겠다.