next up previous contents index Search
Next: Source Code Up: 0.3.2 The Mergesort Previous: Analysis Improvements

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.    

Scott Gasch