#library-sort

Library Sort

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...