Library Sort

Library sort, also called gapped insertion sort, is a sorting algorithm that uses an insertion sort but leaves gaps in the array to accelerate subsequent insertions, named by analogy to a librarian who leaves a space after every letter of the alphabet on a shelf so that a newly acquired book can be inserted without having to move every following book. The algorithm was proposed by Michael Bender, Martin Farach-Colton and Miguel Mosteiro in 2004 and published in 2006; like the insertion sort it is based on, it is a comparison sort, and it was shown to have a high probability of running in O(n log n) time, comparable to quicksort, rather than an ordinary insertion sort's O(n squared), though it requires extra space for its gaps and must randomly permute its input to guarantee that time bound.