science

Library sort

Library sort is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Library sort rather than just read about it. In short: 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: 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.

Key takeaways

Library sort belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Library sort to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Library sort from memory before moving on to harder problems.

Reference excerpt

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:

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. The algorithm was proposed by Michael A. Bender, Martín Farach-Colton, and Miguel Mosteiro in 2004 and was published in 2006. Like the insertion sort it is based on, library sort is a comparison sort; 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(n2). There is no full implementation given in the paper, nor the exact algorithms of important parts, such as insertion and rebalancing. Further information would be needed to discuss how the efficiency of library sort compares to that of other sorting methods in reality. Compared to basic insertion sort, the drawback of library sort is that it requires extra space for the gaps. The amount and distribution of that space would depend on implementation. In the paper the size of the needed array is (1 + ε)n, but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the high-probability time bounds, it must randomly permute the input, which changes the relative order of equal elements and shuffles any presorted input. Also, the algorithm uses binary search to find the insertion point for each element, which does not take advantage of presorted input. Another drawback is that it cannot be run as an online algorithm, because it is not possible to randomly shuffle the input. If used without this shuffling, it could easily degenerate into quadratic behaviour. One weakness of insertion sort is that it may require a high number of swap operations and be costly if memory write is expensive. Library sort may improve that somewhat in the insertion step, as fewer elements need to move to make room, but also adds an extra cost in the rebalancing step. In addition, locality of reference will be poor compared to mergesort, as each insertion from a random data set may access memory that is no longer in cache, especially with large data sets.

Implementation

Algorithm Let us say we have an array of n elements. We choose the gap we intend to give. Then we would have a final array of size (1 + ε)n. The algorithm works in log n rounds. In each round we insert as many elements as there are in the final array already, before re-balancing the array. For finding the position of inserting, we apply Binary Search in the final array and then swap the following elements till we hit an empty space. Once the round is over, we re-balance the final array by inserting spaces between each element. Following are three important steps of the algorithm:

Binary Search: Finding the position of insertion by applying binary search within the already inserted elements. This can be done by linearly moving towards left or right side of the array if you hit an empty space in the middle element. Insertion: Inserting the element in the position found and swapping the following elements by 1 position till an empty space is hit. This is done in logarithmic time, with high probability. Re-Balancing: Inserting spaces between each pair of elements in the array. The cost of rebalancing is linear in the number of elements already inserted. As these lengths increase with the powers of 2 for each round, the total cost of rebalancing is also linear.

Pseudocode procedure rebalance(A, begin, end) is r ← end w ← end × 2

while r ≥ begin do A[w] ← A[r] A[w-1] ← gap r ← r − 1 w ← w − 2

procedure sort(A) is n ← length(A) S ← new array of n gaps

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) insert A[j] at S[ins]

Here, binarysearch(el, A, k) performs binary search in the first k elements of A, skipping over gaps, to find a place where to locate element el. Insertion should favor gaps over filled-in elements.

References

External links Gapped Insertion Sort

Worked examples

Example 1 — a first encounter with Library sort

Start with the simplest possible case. Write down what Library sort claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Library sort before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Library sort ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Library sort

In research: Library sort appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Library sort in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Library sort is common in secondary-school and first-year university syllabi. It links to neighbouring topics Comparison sorts, Online sorts, Stable sorts, so understanding it makes those chapters shorter.
In everyday life: Look for Library sort outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Library sort” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Library sort in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Library sort means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Library sort out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Library sort in simple terms?

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: Suppose a librarian were to store their books alphabetically on a long shelf, starting with the As at the left en…

Why does Library sort matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Library sort?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Library sort.