Intro Sort (인트로 정렬)

 일반적으로 퀵정렬은 평균적으로 O(n log n)이라는 시간복잡도를 갖습니다. 하지만 최악의 경우에는 O(n²)이라는 시간복잡도를 갖게되지요. 개발자들은 퀵정렬의 평균적이라는 장점을 살리고 최악의 경우를 보완하는 알고리즘을 만들고자 했습니다. 즉, 최악의 경우에도 O(n log n)을 만족하고자 하는 것인데요,

 

 결국, 개발자들은 퀵정렬이 최악의 경우에도 시간복잡도가 O(n log n)이 되는 방법을 찾았습니다. 아이디어는 간단합니다. 퀵정렬을 사용하되 다른 알고리즘들과 혼합하여 사용하면 됩니다. 다만 특이한 점은 1차 임계값과 2차 임계값이 존재하여 각 알고리즘 사용 구간을 구분해준다는 점입니다.

 

 맨 처음 정렬에는 퀵소트를 사용합니다. 그리고 재귀적으로 퀵소트를 사용하면서 분할되는 횟수를 스스로 모니터링하다가 1차 임계값에 도달했을 경우, 그 이후의 정렬은 Heap Sort(힙정렬) 방식을 사용하는 겁니다. 그리고 2차 임계값의 원소들에 대해서는 마지막에 삽입정렬을 수행하는 방식이죠.

 

Pseudocode는 아래와 같습니다(위키피디아 참조)

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

procedure introsort(A, maxdepth):
    n ← length(A)
    if n ≤ 1:
        return  // base case
    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[0:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

참고로, maxdepth 변수는 위에서 말한 1차 임계값이며, ( log(length(A))의 under값 ) * 2를 통해 값을 구하게 됩니다. 

 

GCC의 std::sort는 인트로 정렬의 약간 변이된 버전을 사용합니다. 작은 범위의 원소들은 O(n log n)복잡도를 갖는 정렬방식을 사용하는 것 보다는 복잡한 O(n²)의 복잡도를 갖는 정렬방식을 사용하는게 더 빠르기 때문에, 보통 16개 미만의 원소들에 대해서는 보통 삽입정렬을 사용하게 됩니다.