🚀 팀 정렬이란?
Tim sort는 2002년에 Tim Peters라는 개발자가 만든 정렬 알고리즘으로
삽입 정렬(Insertion sort)과 병합 정렬(Merge sort)을 섞은 알고리즘입니다
📌시간 복잡도
🎈 최선: O(n)
배열이 이미 정렬되어있거나 긴 run(부분 배열)이 하나만 존재할 경우 O(n)의 시간복잡도를 가집니다
🎈 평균 및 최악: O(nlogn)
여러 개의 run이 생성되고, 각 run을 삽입정렬하는 과정에서 log n의 시간복잡도가 발생합니다
또한 이 run들을 병합하는 과정에서 n만큼의 시간복잡도가 발생해 전체 시간복잡도는 O(nlogn)입니다
📌공간 복잡도
팀 정렬은 병합 과정에서 두가지 run중 하나만 임시 메모리에 복사해서 사용하기 때문에 공간복잡도 효율이 좋습니다
🎈 최선: O(1)
이미 정렬된 run이 하나만 생기기 때문에 병합이 거의 없어서 추가 메모리를 거의 사용하지 않습니다
🎈 평균: O(logn)
여러 run을 병합하는 과정에서 일부를 임시공간에 저장해야하기 때문에 logn 수준의 추가 메모리가 필요합니다
🎈 최악: O(n/2)
두 run 중 하나가 전체 크기의 첮랍ㄴ에 가까울 경우 해당 run을 복사해야하기 때문에 n/2만큼의 메모리가 필요합니다
📌장점
- 안정 정렬이므로 동일한 값의 순서를 보장합니다
- 데이터가 부분적으로 정렬된 경우 매우 빠릅니다
- 실제 프로그램에서 쓰기 좋게 최적화가 많이 되어 있습니다
참고로 Java에서는Arrays.sort()로 구현되어있습니다
📌 단점
- 완전 무작위 데이터에서는 Quick sort보다 느릴 수 있습니다
✍️ 결론
팀 정렬은 삽입 정렬의 빠른 처리와 병합 정렬의 안정성을 동시에 갖춘 알고리즘입니다
최악의 경우에도 시간 복잡도가 O(nlogn)을 넘지 않고,
병합 시 최대 O(n/2) 수준의 추가 메모리만 사용하기 때문에 효율적인 정렬 알고리즘입니다
참고
Software Developer