팀 정렬 (Tim Sort)의 원리 - 병합정렬
팀정렬의 병합정렬 방식은 기존 병합정렬 방식과 달리 run의 길이가 균등하지 않기 때문에
약간 다르게 접근합니다
스택을 활용한 관리
팀 정렬은 각 run을 생성할 때마다 스택에 저장합니다
이때 스택은 다음 두가지 조건을 항상 만족해야합니다
- 조건 1:
Stack[i] > stack[i-1] + stack[i-2] - 조건 2:
stack[i-1] > stack[i-2]
이 조건을 만족하지 못하는 경우, 인접한 두 스택 덩어리와 비교해서 더 작은 덩어리와 병합합니다
팀 정렬은 병합을 진행할 때 이 두가지 조건을 만족하며
서로 제각각인 덩어리들을 안정적으로 병합합니다
장점
스택의 크기를 작게 유지가능
위 조건을 만족하는 스택을 확인했을 때,
스택에 들어있는 run의 수를 작게 유지할 수 있다는 장점이 있습니다
마치 피보나치 수열과 유사하게 run의 길이를 유지할 수 있으므로
스택의 크기를 작게 유지할 수 있습니다
최소한의 메모리 이용
비슷한 크기의 덩어리를 병합할 수 있습니다
만족하지 못하는 경우도 인접한 덩어리 중 작은 run과 병합하는데,
이것 역시 가장 비슷한 크기의 run과 병합한다는 것을 의미합니다
즉, 비슷한 크기의 덩어리를 병합함으로써 최소한의 메모리를 이용할 수 있고
최고의 효율을 낼 수 있습니다
참고
Software Developer