Content deleted Content added
O(n²) worst-case / O(n log n) average is more similar to quicksort's performance bounds than to mergesort's |
No edit summary |
||
Line 13:
The algorithm was proposed by [[Michael A. Bender]], [[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 |
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.
| |||