Tim Sort

Tim Sort

Various Sort Disadvantage

  • Heap Sort
    • best와 worst case의 시간 복잡도가 다 O(nlogn)
    • 그러나 배열의 i번째 원소와 2 * i 번째 원소를 비교하므로, 공간 지역성의 원리를 만족하지 못함
    • 즉, 캐시 메모리를 잘 활용하지 못함
  • Merge Sort
    • 역시 best와 worst case의 시간 복잡도가 다 O(nlogn)
    • 두 배열의 각각의 인덱스를 증가시키기 때문에 공간 지역성의 원리를 만족
    • 그러나 정렬에 추가적인 메모리 필요
  • Quick Sort
    • 메모리를 추가적으로 사용하지도 않고, 공간 지역성의 원리도 만족
    • 그러나 worst case가 O(n^2)임

Tim Sort

  • 기존 Sort 방법의 문제를 해결하기 위해 등장한 정렬 방법
  • Insertion sort와 merge sort를 병합
  • 최적의 경우 O(n), 평균과 최악의 경우 O(nlogn)
  • 대부분의 프로그래밍 언어에서 표준으로 채용

Tim Sort 원리

  • 작은 n에 대해, insertion sort는 quick sort보다 빠름
  • 위 원리를 활용해, 전체 배열을 작은 덩어리로 쪼개어서 insertion sort를 수행하고 병합하면 효율적이라는 점에서 착안
    • 데이터를 $2^x$ 개씩 쪼개어서 insertion sort를 수행
    • 이후 merge sort를 수행해서 데이터 병합
  • 각 덩어리를 run, $2^x$ 를 minrun이라 부름
  • 동작 순서
    1. run의 첫 두 원소를 비교
    2. 두 번째 원소가 첫 번째 보다 큰 경우, 값을 순차적으로 증가시키는 방향으로 insertion sort (작은 경우는 반대로)
    3. minrun 번째 원소까지 insertion sort를 수행
    4. minrun 다음 원소가 minrun 번째 원소보다 큰 경우, 해당 원소들을 덩어리에 포함
    5. minrun 보다 작은 원소가 나오면 다음 run을 생성해 1번으로 돌아감
    6. 감소하는 run인 경우 뒤집어서 증가하는 run으로 만들고, 이후 merge sort

Insertion Sort 최적화

  • minrun은 min(데이터의 갯수, 2^5 ~ 2^6) 으로 설정
  • Insertion sort 으로 삽입해야 할 위치를 찾을 때 binary insertion sort를 통해 빠르게 위치를 찾음
    • 이렇게 해도 insertion sort 자체의 시간 복잡도는 O(n^2)이나, 시프트 연산이 더욱 빨라짐

Merge Sort 최적화

  • 각 run들이 모두 크기가 다르므로, 일반적인 병합 정렬과 다른 방식 사용
  • 각 run이 만들어질 때마다 stack에 담음
  • 이 때 stack의 각 run 들이 다음 조건을 만족하도록, 작은 run들을 병합
    • stack[i] > stack[i - 1]
    • stack[i] > stack[i - 1] + stack[i - 2]
  • 각 run의 길이가 피보나치 수보다 크므로, stack의 크기가 적당한 수준에서 제한됨
  • 또한 2-run merge 라는 방법을 통해 작은 크기의 run 만 복사하고도 병합 정렬 수행 가능
    • 이 과정을 통해 공간을 최소 절반 이상 아낄 수 있음
  • Galloping이라는 방법을 사용해 merge sort에서 사용되는 index를 최적화해서 움직이기도 함

References

  1. https://d2.naver.com/helloworld/0315536