팀소트

팀소트(Timsort)는 수많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘의 하나이다. 합병 정렬과 삽입 정렬이 기원이다. 2002년 파이썬 프로그래밍에 사용하기 위해 팀 피터스가 구현했다.

팀소트

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	${\displaystyle O(n\log n)}$[1][2]
최선 시간복잡도	${\displaystyle O(n)}$[3]
평균 시간복잡도	${\displaystyle O(n\log n)}$
공간복잡도	${\displaystyle O(n)}$

팀소트는 버전 2.3부터 파이썬의 표준 정렬 알고리즘이다. 자바 SE 7, 안드로이드, GNU 옥타브, V8, 스위프트, 러스트에서 프리미티브가 아닌 타입의 배열을 정렬하기 위해서도 사용된다.

피터 매클로이의 1993년 논문 "최적의 정렬 및 정보이론복잡성"(Optimistic Sorting and Information Theoretic Complexity)의 기법들을 사용한다.