Content deleted Content added
Tag: Reverted |
ClueBot NG (talk | contribs) m Reverting possible vandalism by 2001:16A2:78B5:6500:C50C:5F43:1AA7:8184 to version by David Eppstein. Report False Positive? Thanks, ClueBot NG. (4074689) (Bot) |
||
Line 2:
==Algorithm==
Merge-insertion sort performs the following steps, on an input <math>X</math> of <math>n</math> elements:<ref>The original description by {{harvtxt|Ford|Johnson|1959}} sorted the elements in descending order. The steps listed here reverse the output, following the description in {{harvtxt|Knuth|1998}}. The resulting algorithm makes the same comparisons but produces ascending order instead.</ref>
#Group the elements of <math>X</math> into <math>\lfloor n/2\rfloor</math> pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements.
| |||