Content deleted Content added
→Analysis: reverted an eroneous change of mine |
The third step of the algorithm (about the recursive call) now explicitly states that you have to use the merge-insertion recursively (this part was confusing and led to a lot of misimplementation around me). The Art of Computer Programming, 3rd volume by Donald Knuth explicitly states that the recursion must be made using the merge-insertion algorithm (page 184), and not a mere merge sort |
||
Line 6:
#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, using the merge-insertion sort.
#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.
| |||