[Python] [정렬] Timsort

파이썬의 내장 정렬 함수 sorted()와 리스트의 .sort() 메서드는 시간복잡도 O(n log n)을 가진다.

• sorted()는 새로운 리스트를 반환
• .sort()는 기존 리스트를 제자리(in-place)에서 정렬

파이썬은 정렬을 위해 Timsort라는 알고리즘을 사용
Merge Sort와 Insertion Sort를 결합한 하이브리드 알고리즘

• 최악의 경우 (Worst case): O(n log n)
• 평균적인 경우 (Average case): O(n log n)
• 최선의 경우 (Best case, 거의 정렬되어 있는 경우): O(n)