Next: 0.3.2.3 Source Code
Up: 0.3.2 The Mergesort
Previous: 0.3.2.1 Analysis
One way to improve of the Mergesort algorithm is to reverse the order
of each ``right'' list during its creation. This allows the merge
procedure to work inward from the opposite ends of its two input lists
which, in turn, allows the end of each input list to act as a guard
for the other inside the merge routine and eliminates the need for
special tests to see if a particular input list has been exhausted.
This is discussed more fully in Sedgewick's Algorithms in C.