[정렬 알고리즘] 팀소트(Tim sort)

https://en.wikipedia.org/wiki/Timsort 

Timsort - Wikipedia

 

Timsort

• Peter McIlroy의 1993년 논문인 [Optimistic Sorting and Information Theoretic Complexity]을 적용했다.
• 병합 정렬(폰노이만이 고안한 O(nlogn)정렬으로 안정적인 퍼포먼스를 보여준다.) 및 삽입 정렬에서 파생된 다양한 종류의 실제 데이터에서 정렬이 되도록 설계되었다.
• Operation 원리는 일반적으로 데이터를 삽입할때 병합 기준의 맞춰 데이터가 병합된다. 이렇게 병합된 데이터는 데이터 추출시 전체 목록을 정렬하는 횟수를 줄여준다. 따라서 이미 데이터의 Index 정보를 알고 있다고 가정하고 분포를 추정해 정렬 할 수 있는 것이다.
• 특징으로는 폰노이만의 병합 정렬은 최선의 복잡도가 O(nlogn)임에 반해 팀소트는 O(n)이다.
• Merge space overhead
  • 두 개의 실행 [1, 2, 3, 6, 10] 및 [4, 5, 7, 9, 12, 14, 17]을 병합해야 합니다. 두 실행은 이미 개별적으로 정렬되어 있습니다. 두 번째 실행의 가장 작은 요소는 4이고 순서를 유지하기 위해 첫 번째 실행의 네 번째 위치에 추가해야 합니다(실행의 첫 번째 위치가 1이라고 가정). 첫 번째 실행의 가장 큰 요소는 10이며 순서를 유지하려면 두 번째 실행의 다섯 번째 위치에 추가해야 합니다. 따라서 [1, 2, 3]과 [12, 14, 17]은 이미 최종 위치에 있으며 요소 이동이 필요한 런은 [6, 10]과 [4, 5, 7, 9]입니다. 이 지식을 사용하면 임시 버퍼 크기 4 대신 크기 2만 할당하면 됩니다.
  • min_Y_i max_Y_i   max_X_i max_X_i part 별 블럭단위로 집어넣는 다고 생각하면 편하다.
• 단점 : 입력 크기의 만큼 메모리를 추가로 사용해야한다.