라이브러리 정렬

라이브러리 정렬

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

라이브러리 정렬(library sort, 라이브러리 소트, gapped insertion sort)은 삽입 정렬을 사용하지만 차후의 삽입 속도를 빠르게 하기 위해 배열에 간격을 두는 정렬 알고리즘의 하나이다.

이 알고리즘은 2004년 마이클 A. 벤더, Martin Farach-Colton, 미구엘 모스테이로에 의해 제안되었으며^[1] 2006년 출판되었다.^[2]

기반을 둔 삽입 정렬처럼 라이브러리 정렬은 안정 비교 정렬에 속하며 온라인 알고리즘으로 수행할 수 있다. 그러나 삽입 정렬의 O(n²)보다 퀵 정렬에 맞먹는 O(n log n)의 실행 시간을 보일 가능성이 높은 것으로 입증되었다. 이러한 개선을 위해 사용되는 구조는 스킵 리스트의 것과 매우 비슷하다.

proc rebalance(A, begin, end)
    r ← end
    w ← end * 2
    while r >= begin
        A[w+1] ← gap
        A[w] ← A[r]
        r ← r - 1
        w ← w - 2

proc sort(A)
    n ← length(A)
    S ← new array of n gaps
    for i ← 1 to floor(log2(n) + 1)
        for j ← 2^i to 2^(i+1)
            ins ← binarysearch(A[j], S, 2^(i-1))
            insert A[j] at S[ins]

• Gapped Insertion Sort