Merge-insertion sort: Difference between revisions

Revision as of 23:26, 12 August 2018

Revision as of 03:29, 13 August 2018

Line 2:

==Algorithm==

Merge-insert sort performs the following steps, on an input <math>X</math> of <math>n</math> elements:<ref>The original description by {{rharvtxt|fjFord|c4csJohnson|distrib1959}} sorted the elements in descending order. The steps listed here reverse the output, making the same comparisons but producing 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.

#Perform <math>\lfloor n/2\rfloor</math> comparisons, one per pair, to determine the larger of the two elements in each pair.

#Recursively sort the <math>\lfloor n/2\rfloor</math> larger elements foundfrom toeach be largerpair, creating a sorted sequence <math>S</math> of <math>\lfloor n/2\rfloor</math> of the input elements, in ascending order.

#Insert at the start of <math>S</math> the element that was paired with the first and smallest element of <math>S</math>.

#Insert the remaining <math>\lceil n/2\rceil-1</math> elements of <math>X\setminus S</math> into <math>S</math>, one at a time, with a specially chosen insertion ordering described below. Use [[binary search]] in subsequences of <math>S</math> (as described below) to determine the position at which each element should be inserted.

The algorithm is designed to take advantage of the fact that the binary searches used to insert elements into <math>S</math> are most efficient when(from the subsequencepoint of <math>S</math>view thatof isworst searchedcase hasanalysis) awhen the length of the subsequence that is searched is one less than a [[power of two]]. ToThis orderis because, for those lengths, all outcomes of the elementssearch inuse suchthe asame waynumber of comparisons as toeach getother.{{r|fj}} binaryTo searcheschoose ofan insertion ordering that produces these lengths, consider the sorted sequence <math>S</math> after step 4 of the outline above (before inserting the remaining elements),

and let <math>x_i</math> denote the <math>i</math>th element of this sorted sequence. Thus,

:<math>S=(x_1,x_2,x_3,\dots),</math>

andwhere each element <math>x_i</math> with <math>i\ge 3</math> hasis apaired correspondingwith an element <math>y_i < x_i</math>, knownthat tohas benot smalleryet thanbeen inserted. (There are no elements <math>x_iy_1</math>, thator has<math>y_2</math> notbecause yet<math>x_1</math> beenand inserted<math>x_2</math> intowere thepaired with each sequenceother.) If <math>n</math> is odd, the remaining unpaired element should also be numbered as one of the elements <math>y_i</math>, with an<math>i</math> index greater by onelarger than the largest indexindexes of athe paired elementelements.

With these indices definedThen, the final step of the outline above can be expanded into the following steps:{{r|fj|c4cs|distrib}}

*Partition the uninserted elements <math>y_i</math> into groups with contiguous indexes. There are two elements <math>y_3</math> and <math>y_4</math> in the first group, and the size of each subsequent group equals the number of elements in all previous groups. Thus, the sizes of the groups form a sequence of powers of two: 2, 2, 4, 8, 16, ...

*Order the uninserted elements by their groups (smaller indexes to larger indexes), but within each group order them from larger indexes to smaller indexes. Thus, the ordering becomes