图书馆排序

算法

现在我们有大小为n个元素的数组。我们选择每两个元素之间的空位，那么我们将有一个最大的数组（1 +ε）n。该算法在log n轮中工作。我们通过二分查找来找到插入的位置，然后交换后面的元素，直到我们命中一个空格。一旦结束，我们通过在每个元素之间插入空格来重新平衡最终的数组。
算法根据以下三个重要的步骤：
1. 二分查找：我们在已经插入的元素中，二分查找这个元素应该插入的位置。这可以通过线性移动到阵列的左侧或右侧，如果您点击中间元素中的空格。
2. 插入: 将元素插入到正确的位置，并且通过交换把后面的元素向右移动，直到空格。
3. 重新平衡：在数组中的每对元素之间插入空格。这需要线性时间，并且由于算法只运行log 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]
在这里，binarysearch(A，k)是执行二分查找中的A中的第k个元素，并且跳过空格，找到元素A[j]应该插入的位置。插入应该优于填补元素的空格。