팀소트

1. 개요

팀소트는 대부분의 실제 데이터에 존재하는 정렬된 요소를 활용하여 효율적으로 정렬하는 알고리즘이다. 런(runs)이라고 불리는 정렬된 요소들을 스택에 쌓고, 특정 조건을 만족하면 병합하는 방식으로 작동하며, 입력 크기에 따라 최소 런 크기를 결정한다. 팀소트는 2의 거듭제곱과 유사한 크기의 런을 병합할 때 효율적이므로, minrun을 선택하여 이러한 조건을 만족시키도록 설계되었다. 병합 시에는 공간 오버헤드를 줄이기 위해 이진 검색을 활용하며, 갤로핑 모드를 통해 정렬 속도를 향상시키기도 한다. 팀소트는 최악의 경우 O(n log n)의 시간 복잡도를 가지며, 이미 정렬된 데이터에 대해서는 선형 시간 내에 실행되는 적응형 정렬 알고리즘이다. 하지만, 특정 입력에 대해 스택 크기 관련 버그가 발견되어 수정되었으며, 형식 검증을 통해 안정성을 강화했다.

더 읽어볼만한 페이지

• 안정 정렬 - 합병 정렬
  합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
• 안정 정렬 - 삽입 정렬
  삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다.
• 비교 정렬 - 합병 정렬
  합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
• 비교 정렬 - 퀵 정렬
  퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
• 정렬 알고리즘 - 합병 정렬
  합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
• 정렬 알고리즘 - 퀵 정렬
  퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.