Tim sort

Tim sort란

Tim sort란 2002년 소프트웨어 엔지니어 Tim Peters에 의해 만들어진 정렬 알고리즘입니다. Tim sort는 Insertion sort와 Merge sort를 결합하여 만든 정렬 알고리즘입니다. Tim Sort 알고리즘의 최선 시간 복잡도는 O(n), 평균은 O(nlogn), 최악의 경우는 O(nlogn)입니다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 Merge sort에 비해 적은 추가 메모리를 사용하여 다른 정렬 알고리즘의 단점을 취대한 극복한 알고리즘입니다.

참조 지역성 원리

Tim sort의 기본 원리에 앞서 참조 지역성의 원리를 설명하는 이유는 알고리즘의 실제 동작 시간에 영향을 미치는 요소이고 Tim sort의 장점 중 하나이기 때문입니다. 시간 복잡도가 O(nlogn)이라는 말은 실제 동작시간은 C x nlogn + a라는 의미입니다. 상대적으로 무시할 수 있는 a는 제외하면 nlogn 앞에는 C라는 상수가 곱해져 있어 이 값에 따라 실제 동작 시간에 큰 차이가 생깁니다. 이 C라는 값에 큰 영향을 끼치는 요소가 바로 참조 지역성입니다.
참조 지역성이란 CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이 때의 예측률을 높이기 위해 사용하는 원리입니다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것입니다. 메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있습니다.
참조 지역성 원리의 개념과 함께 Heap sort, Merge sort, Quick sort를 비교해 보겠습니다.

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

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

Quick sort의 경우 pivot 주변에서 데이터의 위치 이동이 빈번하게 발생하기에 참조 지역성이 좋으며 메모리를 추가로 사용하지 않습니다. 하지만 pivot을 선정하는 방법에 따라 최악의 경우 O(n*n)이 될 수 있다는 단점이 있습니다.

Tim sort의 기본 원리

Insertion sort는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하고 있는 것을 확인할 수 있습니다. 이를 토대로 작은 n에 대해서는 Insertion sort가 매우 빠른 속도를 낼 수 있다는 것을 알 수 있씁니다. 이러한 Insertion sort를 이용하여 전체를 작은 덩이롤 잘라 각각의 덩어리를 Insertion sort로 정렬한 뒤 병합하면 좀 더 빠르지 않을까 하는 것이 Tim sort의 기본적인 아이디어 입니다. 전체 덩어리를 2의 지수승 개로 잘라 각각을 Insertion sort로 정렬하면 일반적인 Merge sort보다 덩어리별 x개의 병합 동작이 생략되어 빠른 속도를 유지할 수 있습니다.

Team sort의 최적화 기법

Run

위의 그림을 살펴보면 녹색 부분은 정렬되어 있고 붉은색 부분은 역순으로 정렬되어 있습니다. 이처럼 정렬되어 있거나 역순으로 정렬된 데이터의 묶음을 run이라고 합니다. 그리고 배열 안에는 정렬되지 않은 값을 가지는 부분들도 존재합니다. 그 데이터들의 경우, minrun이라 불리는 일정 단위로 데이터를 자릅니다. mirun의 경우 보통 32 ~ 64 정도의 값을 유지하는데 2의 지수승으로 보통 유지합니다.(2의 지수승으로 유지하는 이유는, 나중에 merge할 때 조건 만족에 수월하기 위해서 입니다.) 그리고 이렇게 임의로 자른 데이터들에 Insertion sort를 적용합니다. 그러고 나면 무작위로 되어 있던 부분들도 정렬이 되어 run이라는 단위가 뒵니다.

Merge

이렇게 만들어진 run 데이터들은 스택에 쌓아둡니다. 두 덩어리를 병합하여 정렬된 하나의 덩어리로 만드는 과정에서 n의 추가 메모리와 두 덩어리의 크기 합만큼의 시간이 소요된다는 것을 확인할 수 있습니다. 그리고 안정성을 유지하기 위하여 인접한 덩어리에 대해 병합을 진행하고, 그 중에서도 비슷한 크기의 덩어리와 병합하여 효율성을 증대시켜야 합니다. 이를 위해 Tim sort는 다음과 같은 규칙을 따릅니다.

Tim sort에서는 하나의 run이 만들어질 때마다 스택에 담아 효율적으로 병합을 진행합니다. 이 때 run을 스택에 push 할 때마다 스택의 맨 위의 세 run이 두 조건을 만족해야 합니다.

위의 그림과 같이 두 조건을 만족하지 않는 상황이 되면 B는 A와 C중 작은 run과 병합됩니다. 병합한 후에도 스택의 맨 위의 세 개의 run이 조건을 만족하지 않으면 조건을 만족할 때까지 병합을 진행합니다.

2Run Merge
위와 같이 병합을 할 때 기존 Merge sort의 가장 큰 단점은 추가 메모리를 n만큼 사용한다는 점이었습니다. 이를 극복하기 위해 Tim sort는 아래와 같은 방법을 사용합니다.

위의 그림은 초록색 run A와 빨간색 run B의 병합 과정을 보여줍니다. 먼저 두 개의 run중 크기가 더 작은 A를 복사합니다. 이후 각 run의 시작 부분부터 크기 비교를 하여 작은 순서대로 앞을 채우면서 병합을 진행합니다. B의 원소가 병합될 때마다 화살표 또한 한 칸씩 앞으로 전진하므로 아직 병합되지 않은 B의 원소의 위치에 따라 다른 수가 적힐 일이 존재하지 않는다는 것을 알 수 있습니다.

Galloping
2Run Merge를 보면 두 run A,B를 병합할 때 화살표가 가리키고 있는 두 원소를 대소 비교하여 병합을 진행했습니다. 여기서 '한 run을 계속해서 참조할 경우가 많지 않을까?'라는 점에 착안하여 Galloping mode일 경우 하나의 run을 빠르게 참조하도록 동작합니다.

위는 이웃한 두 run을 병합하는 과정 중 일부를 표현한 그림입니다. 초록색으로 색칠되어 있는 부분은 run A의 일부, 빨간색으로 색칠되어 있는 부분은 run B의 일부입니다. 처음에는 화살표가 가리키고 있는 두 원소를 대소 비교하여 어느 run의 원소를 넣을지 정합니다. 이 때 B의 원소가 3번 연속으로 병합되었기애 Galloping mode로 전환됩니다. 이 모드에서는 1, 2, 4, 8과 같이 2의 지수승으로 뛰어 넘으며 대소 비교를 진행합니다. 위의 그림에서는 10, 30, 75와 비교하는 것을 알 수 있습니다. 75와 비교하면 70 < 75 이므로 45,50,60,75의 범위에서 이분 탐색을 진행하여 어느 위치까지 병합할지 결정합니다. 이후 다시 하나의 run에서 연속적으로 병합되지 않을 경우 일반적인 방법으로 진행합니다.

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