Editing Merge sort (section)

==Analysis==
[[Image:merge sort algorithm diagram.svg|thumb|right|upright=1.35|A recursive merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort (top-down).]]

In sorting ''n'' objects, merge sort has an [[average performance|average]] and [[worst-case performance]] of [[big O notation|O]](''n''&nbsp;log&nbsp;''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''&nbsp;⌈[[Binary logarithm|lg]]&nbsp;''n''⌉ − 2<sup>⌈lg&nbsp;''n''⌉</sup> + 1), which is between (''n''&nbsp;lg&nbsp;''n'' − ''n'' + 1) and (''n''&nbsp;lg&nbsp;''n'' + ''n'' + O(lg&nbsp;''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|url=https://www.worldcat.org/oclc/849900742|title=Data structure using C++|isbn=978-81-318-0020-1|oclc=849900742|last1=Jayalakshmi|first1=N.|year=2007|publisher=Firewall Media }}</ref>

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>

In the ''worst'' case, merge sort uses approximately 39% fewer comparisons than [[quicksort]] does in its ''average'' case, and in terms of moves, merge sort's worst case complexity is [[big O notation|O]](''n''&nbsp;log&nbsp;''n'') - the same complexity as quicksort's best case.<ref name=":1" />

Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as [[Lisp programming language|Lisp]], where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort.

Merge sort's most common implementation does not sort in place;<ref>{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|p=151}}</ref> therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for variations that need only ''n''/2 extra spaces).