‘The Timsort algorithm used in Python does multiple sorts efficiently because it can take advantage of any ordering already present in a dataset.’
Timsort를 좀 찾아보았다.
Timsort is a hybridstablesorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It uses techniques from Peter McIlroy’s “Optimistic Sorting and Information Theoretic Complexity”, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467–474, January 1993. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently. This is done by merging an identified subsequence, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python’s standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[3] on the Android platform,[4] and in GNU Octave.[5]
Hybrid algorithm 중 하나이며 python 2.3 버전부터 standrard로 사용되고 있으며 java se에서도 기본 Sorting algorithm으로 사용되는듯 하다.
Timsort는 Merge sort에서 변형되었는데 Merge sort는 평균 시간복잡도는 O(nlogn)이며 Worst case에서도 O(nlogn)이다. Quick sort의 시간복잡도 또한 O(nlogn)이지만 Worst case에서는 O(n ^2)이 발생하지만 역으로 정렬되어있을 경우에나 발생하기 때문에 평균적으로 가장 빠른 알고리즘으로 알려져 있다.
그럼에도 불구하고 기본 Sorting algorithm으로 Quick sort가 아닌 Timsort를 채택한 이유, Timsort의 장점은 무엇일까?
위에서 언급한것과 같이 Quick sort는 worst case에 대한 약점을 가지고 있다.
Timsort
Timsort는 merge sort에서 변형이 되었으며 Hybridstable sorting algorithm이다. Timsort는 Quick sort가 좋은 성능을 보이지 못하는 real world data에서도 좋은 성능을 보이며 최악계산량 또한 O(nlogn)으로 안정적인 정렬알고리즘이다. Merge sort와 차이는 미리 어느정도 정렬이 끝난 열(run)로 분할하고 병합한다.
minrun
Timsort는 run 생성시 run의 크기를 동적으로 구한다. run을 만들때 이미정렬된 subsequence기준으로 생성하며 만약 minrun보다 작게되면 insertion sort를 사용한다. mininum run size(minrun)를 구하는 것은 data size에 의해 결정되며 elements가 64보다 작으면 minrun은 64가 되며 이처럼 사이즈가 작은 subsequence의 경우에 Timsort는 insertion sort를 수행하게 된다. 사이즈가 큰 arrays에서는 32~64 범위의 minrun을 가지고 array를 분할시킨다. 이러한 algorithm은 모든 arrays에 수행하며 크기가 64보다 작아질때까지 한다.
Merge
Timsort는 run을 구하고 모든 run이 만들어졌다면 Merge(병합)을 한다. Merge는 2개씩 이루어지며 stack을 이용하여 run을 push하고 앞서 push 되어있던 run과 merge를 하게 된다.
만약 X< Y+Z이면 Y는 X와Z중 작은것과 merge를 수행하게 된다. (서로 인접해 있는 run끼리만 merge를 하는 이유는 stability를 만족시키기 위해서라고 한다. #링크)
Merge memory
Merge sort가 그러하듯 temp memory가 필요하다. Timsort에서는 temp memory의 사이즈를 2개의 runs중에 작은 사이즈를 할당한다. 작은 사이즈의 run을 임시메모리로 복사를 하고 복사된 run과 복사되지 않은 더 큰 사이즈의 run과 merge가 일어나며 merge는 원래 temp memory에 복사한 run의 메모리 시작부분부터 하나씩 저장되게 된다. 이때 binry search를 이용하여 순차적으로 저장하게 된다.
Galloping mode
Timsort에는 galloping mode라는게존재한다. 대부분 merge는 ‘one pair at a time’ mode이다. 보통 merge는 두 run의 요소를 비교하며 merge해나가지만, 하나의 run에서 연속해서 많이(MIN_GALLOP) pop되면 Galloping mode를 호출하게 된다. Galloping mode는 한쪽의 맨 앞의 요소보다도 작은 요소가 다른 쪽의 요소에 있는지 index를 1이 아니라 2n씩 검색주기를 늘리며 검색한다. Galloping mode에 더 자세한건 Wikipedia링크를 첨부하겠다.
Conclusion
Hybrid sorting algorithm답게 내부에 상황에 따라 여러가지 sorting 알고리즘을 적재적소에 사용하고 있다. Quick sort는 단순하고 구현하기는 쉽지만 Timsort를 구현하기는 다소 까다로운 부분이 많다. 그리고 설계당시 강조된 대부분 real-word data는 이미 부분적으로 정렬된것이 존재한다는 가정하에 디자인이 된부분이 핵심이며 이 부분으로 인해 여러 플랫폼들이 기본 sorting algorithm으로 채택한것이 아닐까 싶다.
