Library Sort

Library sort is an insertion-based sorting algorithm that leaves empty spaces between stored elements. These gaps make later insertions cheaper because elements often move only a short distance instead of shifting an entire suffix.

The idea is similar to leaving empty spaces on a bookshelf so new books can be inserted without moving many existing books.

Problem

Given a sequence $A$ of length $n$, reorder it such that

Key Idea

Maintain a larger array with gaps. Insert elements one by one into their sorted position. When gaps become too sparse or poorly distributed, rebalance the structure by spreading elements evenly again.

Algorithm

library_sort(A):
    S = array with extra empty slots
    insert first element into S

    for each remaining element x in A:
        pos = binary_search_position(S, x)

        if S[pos] is empty:
            S[pos] = x
        else:
            move nearby elements until an empty slot is found
            insert x at pos

        if too many insertions since last rebalance:
            spread elements evenly across S

    compact S into A

Example

Suppose the sorted structure currently stores:

[1, _, 3, _, 7, _, 9, _]

Insert $5$.

Its position is between $3$ and $7$, and there is an empty slot nearby:

[1, _, 3, 5, 7, _, 9, _]

Insertions are cheap when gaps are available.

Correctness

The maintained structure always keeps the non-empty entries in sorted order. Each insertion finds the correct sorted position and places the new value there, shifting only as needed to preserve order. Rebalancing changes only the physical positions of elements, not their sorted order. After all insertions, compacting the non-empty entries yields a sorted sequence.

Complexity

With suitable gap management, library sort has expected time:

Worst-case behavior can degrade when gaps are poorly distributed:

Space complexity:

because the algorithm stores extra gaps.

Properties

• stable if insertion is implemented carefully
• not in-place
• insertion-based
• uses extra space to reduce shifting
• expected efficient behavior with rebalancing

When to Use

Library sort is useful as a conceptual improvement over insertion sort when online insertion behavior matters and extra memory is acceptable. It also illustrates a common data-structure tradeoff: reserve unused space now to reduce movement later.

Implementation

This compact version uses a sorted list with binary search. It demonstrates the insertion behavior, though a production implementation would use explicit gaps and rebalancing.

from bisect import bisect_right

def library_sort(a):
    result = []

    for x in a:
        pos = bisect_right(result, x)
        result.insert(pos, x)

    return result

func LibrarySort(a []int) []int {
    result := make([]int, 0, len(a))

    for _, x := range a {
        left, right := 0, len(result)
        for left < right {
            mid := (left + right) / 2
            if result[mid] <= x {
                left = mid + 1
            } else {
                right = mid
            }
        }

        result = append(result, 0)
        copy(result[left+1:], result[left:])
        result[left] = x
    }

    return result
}