Timsort는 merge sort와 insertion sort를 결합한 구조의 정렬 알고리즘이다.

요약

• Timsort는 2002년 python의 기본 정렬 알고리즘으로 설계한 하이브리드 알고리즘
• merge sort와 insertion sort를 정렬한 구조

본문

• 핵심 아이디어: 실제 데이터는 완전 무작위가 아니라 부분적으로 이미 정렬된 구간(run)이 존재한다는 관찰에 기반함

• 로직
  • run 탐지: 배열을 순회하면서 asc, desc로 정렬된 연속 구간(run)을 찾음, 내림 차순 run은 발견 즉시 뒤집에서 오름차순으로 만듦
  • minimum run length (minrun)
    • run 길이가 minrun 보다 짧으면insertion sort로 해당 구간을 minrun 길이까지 확장
  • 병합
    • 확보된 run 들을 스택에 쌓고 스택 invariant을 유지하면서 병합
      • |B| > |A| → 스택 아래로 갈수록 run이 커야 한다
      • |C| > |B| + |A| → 단순히 커지는 정도가 아니라, 피보나치 수열 이상의 속도로 커져야 한다
  • Galloping mode
    • 병합 중 한쪽 run에서 연속적으로 원소가 선택되는 패턴이 감지되면, 지수적 탐색(Galloping)으로 전환해서 비교 횟수를 줄인다.

참고