라이브러리 정렬

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

라이브러리 정렬

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

이 알고리즘은 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]