Content deleted Content added
Added {{refimprove}} tag to article (TW) |
m Open access bot: add arxiv identifier to citation with #oabot. |
||
Line 13:
<blockquote>Suppose a librarian were to store his 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 he finds the correct space in the B section, he 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 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 [[Michael A. Bender]], [[Martín Farach-Colton]], and [[Miguel Mosteiro]] in 2004<ref>{{cite arxiv |arxiv=cs/0407003 |title=Insertion Sort is O(n log n) |date=1 July 2004 |last1=Bender |first1=Michael A. |last2=Farach-Colton |first2=Martín |authorlink2=Martin Farach-Colton |last3=Mosteiro |first3=Miguel A.}}</ref> and was published in 2006.<ref name="definition">{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391–397 | date=June 2006 | last1=Bender | first1=Michael A. | last2=Farach-Colton | first2=Martín | authorlink2 = Martin Farach-Colton | last3=Mosteiro | first3=Miguel A. | title=Insertion Sort is O(n log n) | doi=10.1007/s00224-005-1237-z | url=http://csis.pace.edu/~mmosteiro/pub/paperToCS06.pdf | arxiv=cs/0407003 }}</ref>
Like the insertion sort it is based on, library sort is a [[stable sort|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<sup>2</sup>). The mechanism used for this improvement is very similar to that of a [[skip list]]. 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.
| |||