#08 파이썬 내장 정렬(Tim Sort)

파이썬의 내장 정렬은 Tim sort 알고리즘으로 구현되어있다.

 

tim sort는 삽입 정렬과 병합 정렬을 합쳐서 구현한 알고리즘이다. 최악에 경우에 O(nlogn) 최선의 경우에 O(n)을 보장하는 알고리즘이다.

 

1. 리스트가 주어졌을때 이를 run 단위로 나눈다 (원소의 개수는 32 ~ 64개)

2. run 단위로 나눈 후에 run 단위로 insertion sort를 한다. -> 원소의 개수가 적기 때문에 효율적으로 동작함 O(n) 시간

3. 정렬된 단위별로 merge sort를 진행함.

4. 어떤 순서로 run들을 merge sort 하는지에 대해 stack을 이용하여 결정한다.

 

run 단위로 쪼갬

병합정렬 할 때에 추가 메모리를 작은 run 기준으로 설정

위의 기준으로 run 단위병합 순서를 결정함

추가 메모리를 사용하기 때문에 in-place 알고리즘은 아님, 안정 정렬임