Merge-insertion sort: Difference between revisions

Revision as of 12:14, 19 February 2024

Revision as of 10:16, 20 February 2024

Line 5:

#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 from each pair, 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.