Collections.sort에 쓰이는 TimSort

TimSort

창안자인 Tim Peters의 이름을 따서 팀 정렬(Tim sort) 알고리즘이라고 부른다. 

처음 만들어졌을 때는 Python을 위해 C언어로 구현되었으나 현재 Java, Android, Google Chrome, swift 등에서 표준 정렬 알고리즘으로 채택되었다. 

 

특징

• '실제 데이터는 대부분 이미 정렬되어 있을 것이다.'라는 가정에 기반한 정렬 알고리즘
• 삽입정렬과 병합정렬을 적절히 조합한 알고리즘
• 현업에서 병합정렬, 퀵정렬보다 널리 쓰이는 정렬 알고리즘

시간 복잡도

 

 

현실세계의 데이터들이 완전 무작위로 배열돼 있기 보단 어느 정도 정렬된 상태로 배열돼 있는 경우가 많다면

 

정렬을 해야하는 전체 배열을 작은 덩어리들로 잘라

각각의 덩어리를 Insertion Sort로 정렬한 뒤 Merge Sort로 병합하면 좀 더 빠르지 않을까?

 

 

시간 복잡도가 선형로그시간 즉, O(n log n)라는 말은, 실제 동작 시간이 C x (n log n) + α라는 의미이다.
상대적으로 무시할 수 있는 부분인 α 부분을 제하면
(n log n)에는 앞에 C라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생기는데
이 C라는 값에 큰 영향을 끼치는 요소로
'알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'가 있다.

 

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

쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로
캐시 메모리에 담아놓는 것이다.
메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면,
무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.

 

heap sort

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

 

Quick Sort

pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기에
참조 지역성이 좋으며 메모리를 추가로 사용하지 않는다.
실제로도 C의 값은 다른 두 정렬들보다 작은 값으로 정의되어 있고
평균 시간 복잡도는 셋 중에 가장 빠르다고 알려져 있다.
그러나 pivot을 선정하는 방법에 따라
최악의 경우 이차시간 즉 O(n**2)이 될 수 있다는 단점이 있다."
불안정 정렬이라는 점이 큰 마이너스로 작용한 것으로 보인다.

 

Merge Sort

인접한 덩어리를 병합하기에 참조 지역성의 원리를 어느 정도 잘 만족한다.
입력 배열 크기만큼의 메모리를 추가로 사용한다는 단점이 있지만
상수 C의 값이 너무 커지지 않게 동작하며,
추가 메모리도 많이 사용하지 않고,
최악의 경우에도 선형로그시간 O(n log n)으로 동작하기 때문에
병합정렬이 팀소트에 조합된 것으로 보인다.

 

Insertion Sort

인접한 메모리와의 비교를 반복하기에
참조 지역성의 원리를 매우 잘 만족하고 있는 것을 확인할 수 있다
Insertion sort의 상수 C를 C1, 
정렬 알고리즘 중 C 값이 가장 작다고 알려져 있는 Quick sort의 상수 C 를
C2 라고 할 때,  n이 작다면
C1 x n**2 < C2 x (n log n) 이 성립한다고 한다. 
즉 , 작은 n에 대해선 삽입정렬이 퀵정렬보다 빠르다는 것이다.

 

---

Tim 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이 되도록 변환한다.

 

 

Binary Insertion sort

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

Binary라는 용어에서 알 수 있듯이, 삽입해야 할 위치를 찾을 때까지 비교하는 대신,

앞의 원소들은 모두 정렬되어 있다는 전제를 기반으로 이분 탐색을 진행하여 위치를 찾는다.

 

이분 탐색은 참조 지역성은 떨어지지만 한 원소를 삽입할 때 O(n)번의 비교를 진행하는 대신

O(logn)번의 비교를 진행하기에 작은 n에 대하여 좀 더 시간을 절약할 수 있다.

 

삽입해야 할 위치를 빠르게 찾아도 그 위치에 삽입하는 과정은 O(n)이기에

전체의 시간 복잡도는 O(n^2)으로 일반적인 Insertion sort와 동일하지만

그 위치에 삽입하고 나머지 원소를 시프트하는 연산은 빠르기 때문에 훨씬 효율적이다.

 

Merge

배열을 맨 앞 원소부터 훑으며 run의 크기가 minrun보다 작을 경우 Binary Insertion sort를 진행하고

증가하는 run인지, 감소하는 run인지에 따라 조건에 맞게 최대한 run의 크기를 키우고,

감소하는 run의 경우 뒤집어서 하나의 증가하는 run을 생성했다.

 

우리는 이제 효율적인 방법으로 run들을 병합할 차례이다.

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

 

두 덩어리를 병합하여 정렬된 하나의 덩어리로 만드는 과정에서 n의 추가 메모리와

두 덩어리의 크기의 합만큼의 시간이 소요된다는 것을 확인할 수 있다.

그리고 안정성을 유지하기 위하여 인접한 덩어리에 대하여 병합을 진행했으며,

그 중에서도 비슷한 크기의 덩어리와 병합하여 효율성을 증대시킨 것을 알 수 있다.

 

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

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

 

 

 

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

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

 

 

 

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

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

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

 

규칙은 이렇다.

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

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

 

 

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

 

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

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

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

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

 

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

조건을 만족하지 않을 경우 B는 A와 C 중 작은 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의 맨 앞 원소인 99보다 작기 때문에 병합을 수행하지 않고

현재 위치에 있어도 문제가 되지 않는다.

 

같은 방법으로 run B의 맨 뒤 원소 [13,15,18,21]은 run A의 맨 뒤 원소인 13보다 같거나 크기 때문에

이 원소들 또한 병합을 수행할 필요가 없는 구간이다.

 

이제 [11,13], [9,10] 이렇게 두 부분 run만 병합을 진행하면 되기에

단 4번의 비교와 단 2개의 추가 메모리만으로 병합을 효율적으로 진행할 수 있다.

 

이 필요 없는 구간을 계산하는 과정을 이분 탐색으로 진행할 경우,

run의 길이를 k라 할 때 O(logk)의 시간이 소요된다.

 

이만큼의 추가 시간을 소요하고 더 빠르게 계산이 되면 좋겠지만,

필요 없는 구간이 없을 수도 있기에 오히려 더 늦춰질 수도 있는 최적화 방법이다.

그럼에도 불구하고 실생활 데이터에서 많은 시간을 절약할 수 있기에

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<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(nlogn)이기에 지금까지도 많은 언어에서 표준 정렬 알고리즘으로 채택하여 사용하고 있다.

 

 

https://d2.naver.com/helloworld/0315536