파이썬 리스트 정렬의 숨겨진 비밀: 팀소트(Timsort)는 왜 빠를까요?

파이썬 리스트 정렬의 숨겨진 비밀: 팀소트(Timsort)는 왜 빠를까요?

안녕하세요!

오늘은 파이썬(Python)의 정렬 기능이 왜 생각보다 훨씬 빠른 성능을 보여주는지, 그 비밀의 열쇠인 팀소트(Timsort)에 대해 쉽고 재미있게 파헤쳐 보는 시간을 갖도록 하겠습니다.

마치 한국에서 오랫동안 살아온 사람이 쓴 것처럼 자연스럽게 설명해 드릴 테니, 편하게 따라오시면 됩니다!

팀소트(Timsort)란 무엇일까요?

팀소트(Timsort)는 병합 정렬(merge sort)과 삽입 정렬(insertion sort)의 장점을 결합하여 실제 데이터 환경에서 뛰어난 효율성을 보여주는 정렬 알고리즘입니다.

2002년에 팀 피터스(Tim Peters)라는 분이 고안했는데요.

현재 파이썬(Python)에서는 리스트(list)의 sort() 메서드의 기본 정렬 방식으로 사용되고 있습니다(파이썬 2.3 버전부터 사용되기 시작했습니다).

놀랍게도 이제는 자바 SE7(Java SE7)이나 안드로이드(Android) 운영체제에서도 배열 정렬에 팀소트(Timsort)를 활용하고 있다고 합니다.

팀소트(Timsort)의 핵심 아이디어는 데이터 속에서 이미 정렬된 작은 덩어리들, 즉 '런(run)'이라고 불리는 구간들을 찾아내는 것에서 시작합니다.

그리고 이 '런(run)'들을 특정한 규칙에 따라 효율적으로 합쳐나가면서 전체 데이터를 정렬하는 방식입니다.

1. 팀소트(Timsort)는 어떻게 동작할까요?

우리가 다루는 실제 데이터 대부분은 신기하게도 부분적으로 이미 정렬된 상태를 가지고 있는 경우가 많은데요.

팀소트(Timsort)는 바로 이 점을 영리하게 활용합니다.

팀소트(Timsort)는 개별 숫자가 아닌, 이미 정렬된 데이터 묶음인 '런(run)'을 기본 처리 단위로 삼습니다.

먼저 데이터에서 연속적으로 오름차순이거나 내림차순인 부분을 찾아 하나의 '런(run)'으로 만듭니다.

여기서 중요한 점이 있는데요.

오름차순 런(run)은 a[시작] <= a[시작 + 1] <= a[시작 + 2] <= ... 처럼 다음 원소가 이전 원소보다 크거나 같은 경우를 의미합니다.

반면, 내림차순 런(run)은 반드시 a[시작] > a[시작 + 1] > a[시작 + 2] > ... 처럼 다음 원소가 이전 원소보다 반드시 작아야 합니다.

이렇게 엄격하게 '작은' 경우만 내림차순 런(run)으로 인정하고, 찾아낸 내림차순 런(run)은 내부 원소들의 순서를 뒤집어 오름차순으로 만들어 줍니다.

왜 '크거나 같은' 경우가 아닌 '반드시 작은' 경우만 뒤집을까요?

그 이유는 팀소트(Timsort)가 '안정 정렬(stable sort)'이라는 중요한 특징을 유지하기 위해서입니다.

안정 정렬이란, 같은 값을 가진 원소들의 상대적인 순서가 정렬 후에도 그대로 유지되는 것을 의미합니다.

만약 크거나 같은 경우(>=)도 뒤집게 되면 이 안정성이 깨질 수 있기 때문입니다.

최소 런(run) 길이 정하기

찾아낸 런(run)들은 길이가 제각각일 수 있습니다.

팀소트(Timsort)는 이 런(run)의 길이에 따라 다른 정렬 전략을 사용하기도 하는데요.

예를 들어 런(run)의 길이가 아주 짧다면, 오히려 삽입 정렬(insertion sort) 방식이 더 효율적일 수 있습니다.

그래서 팀소트(Timsort)는 '최소 런 길이(minrun)'라는 기준을 사용합니다.

배열 전체의 원소 개수가 64개보다 작다면, 최소 런 길이(minrun)는 그냥 배열 전체 길이가 됩니다.

즉, 이 경우에는 전체 배열을 대상으로 삽입 정렬(insertion sort)을 수행해서 정렬을 마칩니다.

하지만 배열의 원소 개수가 64개 이상이라면, 최소 런 길이(minrun)는 32에서 65 사이의 값으로 결정됩니다.

이 값은 전체 데이터 크기를 최소 런 길이(minrun)로 나누었을 때, 그 몫이 2의 거듭제곱에 가깝도록 정해집니다.

구체적인 계산 방식은 배열 크기의 이진수 표현에서 앞 6비트를 가져오고, 나머지 비트 중에 1이 하나라도 있으면 1을 더하는 방식으로 결정되는데요.

이 방식은 배열 크기가 64보다 작은 경우를 포함한 모든 상황에 적용될 수 있습니다.

너무 복잡하게 느껴진다면, 그냥 "효율적인 합병을 위해 런(run)들의 길이를 적절하게 조절하는 기준" 정도로 이해해도 좋습니다.

런(run) 길이 최적화하기

만약 찾아낸 런(run)의 길이가 위에서 정한 최소 런 길이(minrun)보다 짧으면 어떻게 할까요?

팀소트(Timsort)는 이 짧은 런(run)의 길이가 최소 런 길이(minrun)에 도달하도록 배열의 다음 원소들을 가져와 삽입 정렬(insertion sort) 방식으로 런(run)에 추가합니다.

이렇게 하면 대부분의 런(run) 길이가 비슷하게 맞춰져서, 이후에 진행될 런(run) 병합 과정의 효율을 높이는 데 도움이 됩니다.

런(run) 병합하기

데이터를 런(run) 단위로 나누고 길이까지 최적화했다면, 이제 이 런(run)들을 합치는 단계입니다.

팀소트(Timsort)는 런(run) 병합의 효율성을 극대화하는 것을 목표로 하는데요.

이를 위해 스택(stack)이라는 자료 구조를 사용합니다.

새로운 런(run)을 찾을 때마다, 해당 런(run)의 배열 내 시작 위치와 길이를 스택(stack)에 저장합니다.

그리고 스택(stack)에 이미 쌓여있는 이전 런(run)들과의 관계를 보고 병합 여부를 결정합니다.

여기서 중요한 원칙이 있습니다.

팀소트(Timsort)는 스택(stack)에서 서로 인접하지 않은 런(run)들은 절대 병합하지 않습니다.

왜냐하면 중간에 다른 런(run)을 건너뛰고 병합하면 원소들의 순서가 꼬일 수 있기 때문입니다.

팀소트(Timsort)는 스택(stack)의 맨 위에 쌓인 3개의 런(run) 길이를 보고 병합 규칙을 적용합니다.

스택(stack) 맨 위부터 차례대로 런(run)의 길이를 Z, Y, X라고 할 때 (즉, X가 가장 최근에 추가된 런), 다음 두 가지 조건이 동시에 만족되지 않으면 Y와 X를 병합합니다.

1. X > Y + Z
2. Y > Z

예를 들어, 만약 X < Y + Z 라면, X와 Y를 병합하여 새로운 런(run)을 만들고 다시 스택(stack)에 넣습니다.

이 과정을 두 조건이 동시에 만족될 때까지 반복합니다.

두 조건이 만족되면 병합을 멈추고, 다음 런(run)을 찾아서 스택(stack)에 추가하는 과정을 계속합니다.

즉, 스택(stack)에 런(run)을 추가할 때마다 이 병합 조건을 확인하고 필요한 병합을 수행하는 것입니다.

런(run) 병합 상세 과정

인접한 두 개의 런(run)을 병합하려면 임시 저장 공간이 필요합니다.

이 임시 공간의 크기는 병합될 두 런(run) 중에서 더 작은 런(run)의 크기만큼만 있으면 됩니다.

팀소트(Timsort)는 먼저 작은 런(run)의 내용을 이 임시 공간에 복사합니다.

그런 다음, 두 런(run)이 원래 차지하고 있던 공간을 활용하여 정렬된 순서대로 원소들을 채워 넣어 병합된 하나의 큰 런(run)을 만듭니다.

단순하게 생각하면, 두 런(run)의 원소를 처음부터 하나씩 비교하면서 병합할 수도 있습니다.

하지만 팀소트(Timsort)는 여기서 더 나아가 '이진 병합(binary merge)'이라는 똑똑한 방법을 사용합니다.

예를 들어, 두 런(run) A와 B를 병합하고 A가 더 작은 런(run)이라고 가정해 봅시다.

A와 B는 각각 이미 정렬된 상태입니다.

이때, B의 첫 번째 원소가 A의 어느 위치에 들어가야 하는지를 이진 검색(binary search)으로 빠르게 찾아냅니다.

마찬가지로, A의 마지막 원소가 B의 어느 위치에 들어가야 하는지도 이진 검색(binary search)으로 찾습니다.

이렇게 양쪽 끝의 위치를 파악하면, 그 위치 바깥쪽에 있는 원소들은 비교할 필요조차 없어져 비교 횟수를 크게 줄일 수 있습니다.

이 방식은 특히 데이터가 무작위 상태일 때보다 어느 정도 정렬된 부분이 있을 때 훨씬 효과적입니다.

갤러핑(Galloping) 모드

위에서 설명한 이진 병합과 유사하게, 병합 과정의 속도를 더욱 높이는 고급 기법도 있습니다.

'갤러핑(Galloping)'이라고 불리는데요.

특정 원소가 다른 런(run)에서 들어갈 위치를 찾을 때, 단순 비교가 아니라 훨씬 큰 폭으로 건너뛰면서 탐색하는 방식입니다.

자세한 내용은 위키피디아(Wikipedia)의 갤러핑 모드(Galloping Mode) 항목을 참조하면 도움이 될 것입니다.

2. 팀소트(Timsort)의 성능은 어떨까요?

팀소트(Timsort)의 핵심 과정 요약

팀소트(Timsort) 알고리즘은 입력 데이터의 오름차순 및 내림차순 특징을 활용하여 정렬 효율을 높입니다.

개별 원소가 아닌, 정렬된 덩어리인 '런(run)'을 기본 단위로 사용합니다.

이 런(run)들을 차례대로 찾아 스택(stack)에 쌓고, 특정 규칙에 따라 인접한 런(run)들을 병합합니다.

이 병합 과정을 모든 런(run)이 소모될 때까지 반복하고, 마지막으로 스택(stack)에 남아있는 런(run)들을 모두 병합하여 최종적으로 하나의 정렬된 런(run)이 남게 되면 정렬이 완료됩니다.

정리하면 팀소트(Timsort) 알고리즘의 처리 과정은 다음과 같습니다.

1. 배열의 길이가 특정 값(예: 64)보다 작으면, 이진 삽입 정렬(binary insertion sort)을 바로 사용합니다.
2. 배열 전체를 스캔하며 오름차순 또는 내림차순의 런(run)을 찾아 스택(stack)에 추가합니다. (내림차순 런은 뒤집어서 오름차순으로 만듭니다.)
3. 런(run)의 길이가 최소 런 길이(minrun)보다 짧으면, 길이를 늘려줍니다.
4. 스택(stack)에 런(run)을 추가할 때마다 병합 규칙(X > Y + Z, Y > Z)을 확인하고, 조건이 만족되지 않으면 인접한 런(run) Y와 X를 병합합니다.
5. 모든 런(run)을 처리한 후 스택(stack)에 남아있는 런(run)들을 최종적으로 하나가 될 때까지 병합합니다.

성능 분석

정보 과학 이론에 따르면, 비교 기반 정렬 알고리즘은 평균적으로 O(n log n)보다 빠를 수 없습니다.

(여기서 'n'은 데이터의 개수를 의미합니다.) 하지만 팀소트(Timsort)는 실제 데이터에 이미 정렬된 부분이 많다는 특징을 활용하기 때문에, 많은 경우 O(n log n)보다 더 빠른 성능을 보여줍니다.

거의 정렬된 데이터에 대해서는 O(n)에 가까운 시간 복잡도를 보일 수도 있습니다!

물론, 완전히 무작위로 섞인 데이터처럼 활용할 정렬된 부분이 전혀 없다면, 팀소트(Timsort)의 시간 복잡도는 다른 효율적인 정렬 알고리즘과 마찬가지로 O(n log n)에 가까워집니다.

다른 비교 기반 정렬 알고리즘들과 시간 복잡도를 비교해 보면, 팀소트(Timsort)는 최선(Best Case), 평균(Average Case), 최악(Worst Case) 모든 경우에 걸쳐 매우 뛰어난 성능을 보이는 것을 알 수 있습니다.

특히, 이미 데이터가 어느 정도 정렬되어 있을 때의 성능 향상이 두드러집니다.

알고리즘	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도	안정성
삽입 정렬	O(n)	O(n^2)	O(n^2)	안정
병합 정렬	O(n log n)	O(n log n)	O(n log n)	안정
힙 정렬	O(n log n)	O(n log n)	O(n log n)	불안정
퀵 정렬	O(n log n)	O(n log n)	O(n^2)	불안정
팀소트(Timsort)	O(n)	O(n log n)	O(n log n)	안정

공간 복잡도 측면에서도 팀소트(Timsort)는 효율적입니다.

최악의 경우, 병합을 위해 원본 데이터 크기의 절반(n/2)에 해당하는 임시 저장 공간이 필요할 수 있습니다.

하지만 최선의 경우, 즉 데이터가 이미 거의 정렬되어 있다면 아주 적은 양의 상수(constant) 공간만으로도 정렬을 수행할 수 있습니다.

알고리즘	공간 복잡도
삽입 정렬	O(1)
병합 정렬	O(n)
힙 정렬	O(1)
퀵 정렬	O(log n) ~ O(n)
팀소트(Timsort)	O(1) ~ O(n)

참고로, 자바 SE 7(Java SE 7)에서 객체(Object) 정렬에 퀵 정렬(Quicksort) 대신 팀소트(Timsort)를 사용하는 이유 중 하나는 바로 '안정성(stability)' 때문입니다.

퀵 정렬(Quicksort)은 불안정 정렬(unstable sort)인 반면, 팀소트(Timsort)는 안정 정렬(stable sort)이기 때문에 같은 값의 원소들의 기존 순서를 보장해야 하는 경우에 더 적합합니다.

자바 SE 7(JSE 7)의 팀소트(Timsort) 구현 코드 주석에는 팀소트(Timsort)의 장점을 잘 설명하는 다음 구절이 있습니다:

"부분적으로 정렬된 배열에 대해 실행될 때 n log n보다 훨씬 적은 비교 횟수를 요구하는 안정적이고 적응적이며 반복적인 병합 정렬입니다.

동시에 무작위 배열에 대해서는 전통적인 병합 정렬과 비슷한 성능을 제공합니다.

모든 적절한 병합 정렬처럼 이 정렬은 안정적이며 최악의 경우 O(n log n) 시간 복잡도로 실행됩니다.

최악의 경우 이 정렬은 n/2개의 객체 참조를 위한 임시 저장 공간이 필요합니다.

최선의 경우 작은 상수 크기의 공간만 필요합니다."

결론적으로 팀소트(Timsort)는 안정적이면서도 실제 데이터의 특성을 활용하여 평균적으로 매우 빠른 성능을 내는 똑똑한 정렬 알고리즘이라고 할 수 있습니다.

파이썬(Python) 리스트(list)의 sort()가 왜 그렇게 효율적인지, 이제 그 비밀을 아셨으리라 생각합니다!

---