Content deleted Content added
→Optimizing merge sort: Added 2024 peer-reviewed “Divide Smart and Conquer” merge-sort study (FGCS 157) to the Optimizing merge sort section with full {{cite journal}} reference. Tags: Mobile edit Mobile web edit |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed access-date with no URL. | Use this bot. Report bugs. | #UCB_CommandLine |
||
Line 227:
In sorting ''n'' objects, merge sort has an [[average performance|average]] and [[worst-case performance]] of [[big O notation|O]](''n'' log ''n'') comparisons. If the running time (number of comparisons) of merge sort for a list of length ''n'' is ''T''(''n''), then the [[recurrence relation]] ''T''(''n'') = 2''T''(''n''/2) + ''n'' follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the ''n'' steps taken to merge the resulting two lists).<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=36}}</ref> The closed form follows from the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]].
The number of comparisons made by merge sort in the worst case is given by the [[sorting number]]s. These numbers are equal to or slightly smaller than (''n'' ⌈[[Binary logarithm|lg]] ''n''⌉ − 2<sup>⌈lg ''n''⌉</sup> + 1), which is between (''n'' lg ''n'' − ''n'' + 1) and (''n'' lg ''n'' + ''n'' + O(lg ''n'')).<ref>The worst case number given here does not agree with that given in [[Donald Knuth|Knuth]]'s ''[[Art of Computer Programming]], Vol 3''. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal</ref> Merge sort's best case takes about half as many iterations as its worst case.<ref name=":1">{{Cite book
For large ''n'' and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches ''α''·''n'' fewer than the worst case, where <math>\alpha = -1 + \sum_{k=0}^\infty \frac1{2^k+1} \approx 0.2645.</math>
Line 321:
|pages=330–343
|doi=10.1016/j.future.2024.03.049
|doi-access=free}}</ref>
| |||