Timsort - 구현 미정

소스짜다 문득 생각들었다.

 

도대체, python 의 sort 함수는 어떤식으로 정렬을 하길래 이정도 속도를 보여주는가?

 

찾아보니

 

java 의 sort 와 python의 sort 그 외의 다수의 플랫폼에서의 내장형 sort 함수는 이 알고리즘을 기반으로 사용한다고 한다.

 

평균 시간복잡도는 best case 의 경우 O(n) 이고, 평균적으로는 O(nlogn), 최악의 경우에도 O(nlogn) 의 성능을 보여준다고 하니 괜찮은 성능을 보여준다. (적어도 버블처럼 n^2 까진 안가니까)

 

timsort 작업 순서로 크게

1. minimum size 를 최적화

2. merge 정렬

3. insert 정렬

위와 같은 순서로 돌아간다고 하는데...

 

나중에 한번 구현해봐야겠다.

 

Timsort ( wikipedia EN )

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

 

Tim sort 에 대해 알아보자 - NAVER D2

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

 

소스들

https://github.com/timsort/cpp-TimSort

https://www.geeksforgeeks.org/timsort/