Library sort, or gapped insertion sort is a sorting algorithm much like insertion sort but with unused spaces ("gaps") left in the array being sorted to accelerate subsequent insertions. The benefit is that insertions need only shift elements over until a gap is reached. It was invented in 2004 by Bender, Farach-Colton, and Mosteiro. Surprising in its simplicity, they show that this sorting algorithm runs with high probability in O(n log n) time, much like the randomized variant of quicksort.

Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm.

References

• Original publication at Citeseer
• Original publication from xxx.lanl.gov E-Print Archive describing library sort and analyzing its algorithmic complexity.

Sort algorithms | Comparison sorts | Stable sorts