알고리즘 강의를 들었다면, 가장 빠른 정렬 알고리즘이 뭐냐는 질문에 곧장 Quicksort 라고 답할 수 있을 것이다. 실제로 현업에서도 적용하기 가장 편하기 때문에 많이 차용되는 편이다. 그런데 모든 문제를 쉽게 풀 수 있는 은탄은 세상에 존재하지 않듯, Quicksort 역시 특정 케이스에서는 성능이 낮게 나오는 경우가 있다. 더 심각한(?) 것은, 이 특정 케이스가 현실에서는 꽤나 자주 발생한다는 것이다.
그 케이스란 바로 ‘거의 정렬된 데이터’ 이다. 거의 정렬된 데이터라면 pivoting – partitioning 을 반복할 필요도 없이 Bubble Sort 나, 심지어는 Insertion Sort 를 해도 된다. Bubble Sort 의 경우엔 알고리즘 복잡도가 n2 이지만 compare 과정에서 조기에 끝날 가능성이 매우 높아 비용이 거의 발생하지 않을 것이고, Insertion Sort 도 비슷한 이유로 빠르게 끝날 것이다. 하지만 모든 정렬 케이스가 거의 정렬된 데이터만 있지 않기 때문에 쓰지 않는 것일 뿐이다.
만약에 데이터 순열이 ‘**거의 정렬된 데이터의 N 벌’**이라고 하자. 1, 2, 3, …, 10, 2, 3, 4, …, 20 이런 식으로 말이다. (여기서는 2벌) 그림을 그리자면 산이 N 개 생긴 것 처럼 보일 것이다. 이런 경우에는 Bubble Sort 가 큰 힘을 쓰지 못한다. 특정 원소가 산의 제 위치에 찾아가야 하는데, 조기에 끝났던 아까의 경우와는 달리 재수가 없다면 거의 모든 원소 개수와 비교해 봐야 하기 때문이다. 이럴 경우 역시 특효약이 있는데, 산마다 Mergesort 를 하면 쉽다.
오늘 이야기할 Timsort 는 Mergesort 의 변형이라고 보면 된다. 아까 ‘산마다 Mergesort’ 를 한다고 했는데, 어느 지점부터 산으로 봐야할지를 판단하는 알고리즘이 선행된다. 그리고 Mergesort 도 단순히 1개씩 건너뛰는 방법에서 좀 더 나은 방법을 제시한다.
결론부터 말하자면 Timsort 는 무작위 데이터에서 Quicksort 보다 뒤쳐진다. 프로젝트할 때 적용해 본 결과로는 30~50% 정도 느렸다. 하지만 말했다시피, 현실 데이터는 어느 정도 정렬된 데이터의 덩어리를 가지고 있는 경우가 매우 많기 때문에, 그 부분에서는 확실한 성능 차이를 보였다.
자, 이제 한 번 알아보자.
1단계 : Run
데이터 순열에서 이미 정렬이 끝난 부분 데이터들을 Run 이라고 한다. 1, 2, 1, 2, 3, 1, … 같이 주어졌을 때, 1, 2 와 1, 2, 3 을 Run 으로 인식하는 것이다. Timsort 에서는, 데이터 순열을 이런 Run 들로 찾거나 만들어서 확보하는 과정을 거친다. 이게 1단계이다.
Timsort 는 Run 이 너무 짧으면 나중에 의미가 없으므로, 최소 길이를 정해서 Run 을 만들도록 한다. 보통은 길이가 16인 Run 부터 의미있게 쓰길래, 나도 똑같이 16으로 조건을 설정했다.
Run 은 데이터 처음부터 정렬되어 있는 위치까지를 찾는다. 이 길이가 16 미만이라면, 해당 범위는 기억해 두고 다음 Run 을 찾는다. 이렇게 길이가 16 이상의 Run 을 만들 수 있는데, 이 때 쓰는 알고리즘은 사실 아무거나 가져다 써도 된다. 길이가 짧을 때의 정렬 알고리즘은 어느 것을 쓰나 대동소이하기 때문에, 나는 Insertion Sort를 썼다.
2단계 : Merge
1단계 이후로는, 이제 데이터 순열에 Run 여러개가 연속되어 있다. 만약 Run 이 1개뿐이라면? 축하한다. 아주 작은 원소 개수를 정렬하려 했거나, 이미 정렬된 데이터를 넣었단 것이니 이번 단계를 하지 않아도 된다.
앞의 두 Run 을 불러서 Mergesort 하면 되는데, 여기서 Timsort 만의 트릭이 두 개 존재한다.
하나는, Merge 에 참여할 두 Run 의 최소값/최대값을 서로 비교해서, 아예 이긴 구간이나 아예 진 구간을 미리 산정해 두는 것이다. 이 부분은 사실상 Mergesort 과정에서 비교 대상이 될 필요가 없다. 괜한 compare 연산만 낭비하지 말고 처음에 (혹은 나중에) 순순히 들어와주기만 하면 된다. 이 전처리 과정이 끝나면, 남아있는 Run 끼리 Merge 과정을 거친다.
두 번째는, Merge 과정에서 만약 한 쪽이 계속 이기는 상황 (오름차순 정렬이라고 가정했을 때, 한 쪽의 Run 이 계속 작은 원소를 가지고 있을 때) 라면 더 이상의 비교는 무의미하다. 이런 연속 위닝 회수를 정해서, 이후에는 ‘어디까지 이기는지 binary search 로 찾아서 한 번에 그냥 옮기자’ 라는 건너뛰기 모드 (galloping mode) 로 전환된다. 코드를 참조했을 땐, 이 위닝 회수는 3이었다. 스윕승?
건너뛰기 모드 (galloping mode) 에서는, 지고 있던 Run 의 첫 번째 원소가 이기고 있던 Run 의 어느 원소에서 비로소 이기는지를 찾는 것이다. 처음엔 한 칸, 다음엔 두 칸, 그 다음엔 네 칸씩 뛰며 이길 때 까지 찾는다. 그러다가 찾았다면, 직전 구간 사이를 Binary Search 를 통해 최초로 이긴 위치를 찾아내면 된다.
그 다음은? 이기고 있던 Run 의 처음부터 발견된 위치 직전까지를 통째로 memcpy 하면 된다.
마치며
이걸 구현할 때는 급한 나머지 그냥 구현했었는데, (물론 어딘가에선 하고 있겠지만) Mergesort 자체가 병렬 구현이 가능하므로 Timsort 역시 병렬 구현이 가능하리라 본다. Run 을 만드는 작업은 병렬로 할 수 있을까 고민이 되지만, Merge 과정은 작업 큐만으로도 쉽게 그려낼 수 있다.
역시 이것도 만병통치약이 될 수 없다. 상황에 맞춰 적절히 섞어써야 한다. 이런 정렬 알고리즘도 있구나 하며 배웠던 소중한 기회로 여기고 있다.