Content deleted Content added
→In sorting: gloss bracket |
|||
Line 56:
#* Add the Cartesian tree children of the removed value to the priority queue
As Levcopoulos and Petersson show, for input sequences that are already nearly sorted, the size of the priority queue will remain small, allowing this method to take advantage of the nearly-sorted input and run more quickly. Specifically, the worst-case running time of this algorithm is <math>O(n\log k)</math>, where <math>n</math> is the sequence length and <math>k</math> is the average, over all values in the sequence, of the number of consecutive pairs of sequence values that bracket the given value (meaning that the given value is between the two sequence values). They also prove a lower bound stating that, for any <math>n</math> and (non-constant) <math>k</math>, any comparison-based sorting algorithm must use <math>\Omega(n\log k)</math> comparisons for some inputs.{{sfnp|Levcopoulos|Petersson|1989}}
===In pattern matching===
| |||