Timsort

학부에서 알고리즘 수업을 들으면, 가장 빠른 정렬 알고리즘이 뭐냐는 질문에 쉽게 Quicksort 라고 답할 수 있겠다. 실제로 현업에서도 적용하기 가장 편하기 때문에 많이 차용되는 편이다. 그런데 모든 문제를 쉽게 풀 수 있는 은탄은 세상에 존재하지 않듯, Quicksort 역시 특정 케이스에서는 성능이 낮게 나오는 경우가 있다. 더 심각한(?) 것은, 이 특정 케이스가 현실에서는 꽤나 자주 발생한다는 것이다.

그 케이스란 바로 ‘거의 정렬된 데이터’ 이다. 거의 정렬된 데이터라면 pivoting – partitioning 을 반복할 필요도 없이 Bubble Sort 나, 심지어는 Insertion Sort 를 해도 된다. Bubble Sort 의 경우엔 알고리즘 복잡도가 n이지만 compare 과정에서 조기에 끝날 가능성이 매우 높아 비용이 거의 발생하지 않을 것이고, Insertion Sort 도 비슷한 이유로 빠르게 끝날 것이다. 하지만 모든 정렬 케이스가 거의 정렬된 데이터만 있지 않기 때문에 쓰지 않는 것일 뿐이다.

더 읽어보기