라이브러리 정렬

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

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

기반을 둔 삽입 정렬처럼 라이브러리 정렬은 안정 비교 정렬에 속하며 온라인 알고리즘으로 수행할 수 있다. 그러나 삽입 정렬의 O(n2)보다 퀵 정렬에 맞먹는 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

정렬 알고리즘
비교 정렬
안정 정렬
온라인 정렬