Library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
The algorithm was proposed by Michael A. Bender, Martín Farach-Colton, and Miguel Mosteiro in 2006.
Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm; however, it was shown to have a high probab...
more
Library sort, or gapped insertion sort is a sorting algorithm that uses an insertion sort, but with gaps in the array to accelerate subsequent insertions. The name comes from an analogy:
The algorithm was proposed by Michael A. Bender, Martín Farach-Colton, and Miguel Mosteiro in 2006.
Like the insertion sort it is based on, library sort is a stable comparison sort and can be run as an online algorithm; however, it was shown to have a high probability of running in O(n log n) time (comparable to quicksort), rather than an insertion sort's O(n). Its implementation is very similar to a skip list. The drawback to using the library sort is that it requires extra space for its gaps (the extra space is traded off against speed).
less
