Library sort: Difference between revisions

Content deleted Content added
Citation bot (talk | contribs)
Alter: template type. Add: s2cid, eprint. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 1696/1776
top: plainer words
Line 17:
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(n<sup>2</sup>). 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 bedepend implementationon dependentimplementation. In the paper the size of the needed array is ''(1 + ε)n'',<ref name="definition" /> but with no further recommendations on how to choose ε. Moreover, it is neither adaptive nor stable. In order to warrant the with-high-probability time bounds, it requires to randomly permute the input, what 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 profit 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.