🛠️ 팀 정렬(Tim Sort) 동작 원리

팀 정렬(Time Sort)는 삽입 정렬(Insertion Sort)와 병합 정렬(Merge Sort)를 합친 정렬 알고리즘입니다

그런데 평균적인 경우 O(n^2)의 시간복잡도가 발생하는 삽입정렬을 팀 정렬의 동작방식으로 선택한 이유가 뭘까요?

📌 삽입 정렬이 선택된 이유

팀 정렬(Tim sort)에 삽입 정렬(Insertion sort)이 사용된 이유는 작은 크기의 데이터에서 성능이 좋기 때문입니다

삽입 정렬은 데이터 크기가 작을 때,
연속된 메모리의 접근이 잦아 참조 지역성(Locality of Reference) 의 이점을 누릴 수 있습니다
이로 인해 CPU 캐시 활용도가 높아져 매우 빠르게 동작합니다

이를 퀵 정렬(Quick sort)과 비교할 때의 성능을 수식으로 나타내보겠습니다.

• C_i: 삽입 정렬의 상수 (비교와 교환 등 기본 연산이 매우 간단하여 값이 작음)
• C_q: 퀵 정렬의 상수 (비교적 복잡한 연산과 분기 예측 실패로 값이 더 큼)

이때 작은 데이터 크기 n에 대해 다음 식이 성립합니다
C_i × n^2 < C_q × nlog⁡n
즉, 데이터의 크기 n이 작다면, 삽입 정렬이 퀵 정렬보다 더 빠릅니다

✍️ 정리

팀 정렬은 삽입정렬과 병합정렬을 합친 정렬 알고리즘입니다

이때, 평균적으로 성능이 좋지 않은 삽입 정렬을 사용한 이유는
작은 크기의 데이터셋에서 참조 지역성의 이점을 누릴 수 있기 떄문입니다

참고

• Naver D2 - Tim sort에 대해 알아보자