인트로 정렬

인트로 정렬(introsort)은 평균적으로 빠른 성능을 내면서 최악의 조건에서도 점진적으로 최적화된 성능을 제공하는 하이브리드 정렬 알고리즘이다. 퀵 정렬로 시작한 다음 재귀 깊이가 정렬 대상 요소의 수의 레벨(로그)을 초과할 때 힙 정렬로 전환하며 요소들의 수가 특정 임계치 미만일 때 삽입 정렬로 전환한다. 3가지 알고리즘의 좋은 부분을 합쳐놓은 것이며 인트로 정렬이 사용하는 이 3가지 알고리즘들은 비교 정렬이기 때문에 인트로 정렬 또한 비교 정렬이다.

인트로 정렬

분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	O(n log n)
평균 시간복잡도	O(n log n)

Musser(1997)에서 David Musser가 발명하였다. 그는 또, 인트로셀렉트라는 퀵셀렉트 기반 하이브리드형 선택 알고리즘를 선보이기도 했다.

의사코드

procedure sort(A : array):
    let maxdepth = ⌊log2(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n < 16:
        insertionsort(A)
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[1:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

참고 자료

• Musser, David R. (1997). “Introspective Sorting and Selection Algorithms”. 《Software: Practice and Experience》 27 (8): 983–993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#.
• Niklaus Wirth. Algorithms and Data Structures. Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.