Library Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Library Sort

A gapped variation of Insertion Sort: leaves empty slots (gaps) in the array, allowing elements to be inserted in \(O(1)\) shift time on average by avoiding massive shifts.

How it works

Library Sort (also known as Gapped Insertion Sort) was proposed by Michael A. Bender, Martín Farach-Colton, and Miguel Mosteiro in 2004. Its name comes from a real-world analogy: a librarian leaving empty space on shelves to insert new books easily without shifting all subsequent books. The algorithm works as follows:

1. **Gapped Array Allocation:** Allocate a target array larger than the input size (typically of size \((1 + \epsilon) \cdot n\), where \(\epsilon = 1.0\) representing a 50% gap density). Fill the array with placeholder gaps (represented by 0).
2. **Gapped Insertion Loop:** For each element in the input:
   • Use **Binary Search** to find the correct sorted insertion position among the active non-gap elements.
   • Insert the element at the position. If the slot is empty (a gap), write it directly.
   • If the slot is full, shift elements to the right or left until the nearest gap is encountered. Because gaps are frequent, the shift length is \(O(1)\) on average.
3. **Rebalancing:** When the array fills up to its threshold, redistribute the elements evenly across a larger range, inserting new gaps between them.
4. **Compression:** Once all elements are inserted, compress the array by removing all gaps to return a contiguous sorted list.

Complexity

Interactive visualization

Pseudocode

procedure librarySort(A):
  n ← length(A)
  gappedArray ← array of size 2n filled with GAPS
  
  for each element in A:
    pos ← binarySearchNonGaps(gappedArray, element)
    insertAndShiftToNearestGap(gappedArray, pos, element)
    
    if isFull(gappedArray):
      rebalanceAndSpread(gappedArray)
      
  compressAndCopyBack(gappedArray, A)

JavaScript implementation

function librarySort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  // Simulate a simplified gapped array of size 2n
  let gapped = new Array(2 * n).fill(0);
  gapped[n] = arr[0];
  
  for (let i = 1; i < n; i++) {
    const val = arr[i];
    let pos = findInsertPos(gapped, val);
    
    insertAndShift(gapped, pos, val);
    
    // Rebalance when 50% full
    if (countNonGaps(gapped) >= gapped.length / 2) {
      gapped = rebalance(gapped);
    }
  }
  
  // Compress back
  const compressed = gapped.filter(x => x !== 0);
  for (let i = 0; i < n; i++) arr[i] = compressed[i];
  return arr;
}

Pros and cons

When (not) to use it

• Dynamic Databases: Broadly utilized in database index layout tables (like B-Trees) where items are constantly inserted and rebalanced with free space.
• Simple arrays: Avoid; in-memory comparison sorts like Quicksort or Timsort are easier to implement and run faster.