무엇이 Tim Sort인가?

Tim Sort는 Merge Sort와 Insertion Sort의 장점을 결합하여 만들어진 하이브리드 정렬 알고리즘입니다.
Python, Java 등 여러 프로그래밍 언어에서 기본 정렬로 사용되고 있습니다.

Tim Sort 핵심 아이디어 요약

요소	설명
Run	배열에서 증가하거나 감소하는 부분 배열(덩어리)
Binary Insertion Sort	작은 Run들을 빠르게 정렬
Merge Sort	정렬된 Run들을 병합
Stack 구조	Run들을 메모리 효율적으로 병합하기 위해 사용
Galloping Mode	병합 시 두 Run 중 한 쪽이 계속 이기면 빠르게 Merge
Locality of Reference	CPU 캐시 친화적으로 동작 (Insertion Sort 사용)

Step by Step Tim Sort + 시간복잡도

Step 0: Run 탐색

• 배열을 증가하거나 감소하는 구간(run)으로 나눕니다.
• 감소하는 경우 역순 정렬(reverse) 후 사용합니다.
• 정렬된 데이터에 최적화 → 실제 사용 데이터는 대부분 어느 정도 정렬되어 있음.

자연스러운 Run을 찾는 과정

예시:
배열: [1, 2, 3, 7, 6, 4, 5, 8]
Run: [1,2,3,7], [6,4] (→ 역순 정렬 후 [4,6]), [5,8]

시간복잡도: O(n)

• 한 번 순회하며 run을 찾음

Step 1: minrun 정렬 (Binary Insertion Sort)

• 각 Run의 길이가 MIN_RUN보다 작으면, Binary Insertion Sort를 사용해 정렬합니다.
• Binary Insertion Sort는 일반 Insertion Sort보다 빠름 (O(n log n) vs O(n²))

시간복잡도: O(n log k) where k is Run length (작음, 보통 32)

Step 2: Stack에 Run 저장

• Run 병합을 위해 stack에 쌓아 저장함
• 스택을 사용해 Run 간의 병합 조건을 유지하며 merge 수행
  병합 규칙 (3가지):
• X > Y + Z, Y > Z, 등 특정 조건을 만족하지 않으면 merge 수행
• 이 조건들은 메모리 효율성과 안정성 유지를 위한 것

공간 효율성

→ Stack을 이용해 Run들을 관리하므로 병합 시 필요한 임시 버퍼 최소화

Step 3: Run 병합 (Merge Sort 방식)

• Stack의 top 2 또는 3개의 Run을 조건에 따라 병합
• 병합 과정은 Merge Sort와 유사하지만 Galloping Mode (가속 모드)로 동작
  • 병합 도중 한 Run이 연속으로 승리하면, 이진 탐색 기반으로 빠르게 복사

  예: Left = [1,2,3,4,5], Right = [100,101,...]
      병합 시 Left가 계속 이기므로 Galloping으로 Left 전부 복사

시간복잡도: O(n log n) (최악), O(n) (거의 정렬된 데이터)

Locality of Reference란?

• 현대 CPU는 메모리 접근 시 참조 지역성(Locality of Reference)을 활용함
• Insertion Sort는 바로 이 특성에 매우 적합

예시:

• 데이터가 메모리에 연속 저장됨
• 이웃한 데이터를 반복 접근하므로 캐시 히트율 ↑

Tim Sort는 작은 Run에 Insertion Sort를 적용 → Locality를 극대화
→ Merge Sort는 캐시 효율이 낮음 (임시 버퍼를 자주 씀)

공간 효율성: Merge Sort보다 좋은 이유

항목	Merge Sort	Tim Sort
임시 버퍼 사용	O(n)	O(n) (하지만 Stack 병합으로 덜 사용함)
정렬된 부분 활용	❌ 없음	✅ Run 기반 정렬
작은 Run 정렬	❌ 전역 병합	✅ Insertion Sort (캐시 친화적)
메모리 접근	무작위	✅ Locality 우수
메모리 사용	많음	✅ 적음 (Stack, Run 병합 제한)

• 최악의 경우 필요한 임시 저장 공간의 크기는 N/2에 가깝지만, Tim Sort는 스택을 이용한 병합 전략 덕분에 대부분의 경우 O(log n)에 가까운 공간만 사용합니다. 작은 Run들을 병합할 때는 더 적은 임시 공간(예: Run의 크기)만 필요하기 때문입니다.

시간복잡도 요약

단계	시간복잡도
Run 탐색	O(n)
Run 정렬 (Binary Insertion Sort)	O(n log k)
병합 (Merge Sort + Galloping)	O(n log n)
최선 (거의 정렬됨)	O(n)
평균/최악	O(n log n)
공간 복잡도	O(n) (하지만 Merge Sort보다 효율적)

최종 요약

특징	설명
병합 기반	Merge Sort처럼 안정 정렬
캐시 친화적	작은 Run을 Insertion Sort로 정렬 (Locality 효과 극대화)
공간 효율	Stack으로 병합 관리, Merge Sort보다 메모리 효율 좋음
Galloping	병합 가속 기능
증가/감소 Run 자동 탐색	실제 데이터 패턴 활용 (현실적 최적화)

Reference

• Tim sort에 대해 알아보자