Library sort: Difference between revisions

Revision as of 21:48, 14 April 2023

Latest revision as of 10:17, 19 January 2025

(3 intermediate revisions by 3 users not shown)

Line 1:

{{Short description|Sorting algorithm}}

{{refimprove|date=October 2017}}

{{Infobox Algorithm

Line 10 ⟶ 11:

|optimal=?

}}

'''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:

<blockquote>Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Zs. If the librarian acquired a new book that belongs to the B section, once they find the correct space in the B section, they will have to move every book over, from the middle of the Bs all the way down to the Zs in order to make room for the new book. This is an insertion sort. However, if they were to leave a space after every letter, as long as there was still space after B, they would only have to move a few books to make room for the new one. This is the basic principle of the Library Sort.</blockquote>

Line 51 ⟶ 52:

'''for''' i ← 1 to floor(log2(n-1)) '''do'''

rebalance(S, 1, 2^(i-1)))

'''for''' j ← 2^(i-1) to 2^i '''do'''

ins ← binarysearch(A[j], S, 2^i)

Line 66 ⟶ 67:

{{sorting}}

[[Category:Sorting algorithms]]

[[Category:Comparison sorts]]

[[Category:Stable sorts]]