Library sort: Difference between revisions

Revision as of 19:22, 20 June 2014

Revision as of 10:12, 17 July 2014

Line 12:

<blockquote>Suppose a librarian were to store his books alphabetically on a long shelf, starting with the A's at the left end, and continuing to the right along the shelf with no spaces between the books until the end of the Z's. If the librarian acquired a new book that belongs to the B section, once he finds the correct space in the B section, he will have to move every book over, from the middle of the B's all the way down to the Z's in order to make room for the new book. This is an insertion sort. However, if he were to leave a space after every letter, as long as there was still space after B, he 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>

The algorithm was proposed by [[MichaelRaman A. BenderKumar]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>http://arxiv.org/abs/cs/0407003</ref> and was published in 2006.<ref name="definition">

{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391 | year=2006 | author=Bender, M. A., Farach-Colton, M., and Mosteiro M. | title=Insertion Sort is O(n log n) | doi = 10.1007/s00224-005-1237-z }}</ref>