Two-Way Merge Sorting

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Two-Way Merge Sorting

Program gives the code for two Sort methods of the TwoWayMergeSorter class. The no-arg Sort method sets things up for the second, recursive Sort method. First, it allocates a temporary array, the length of which is equal to the length of the array to be sorted (line 7). Then it calls the recursive Sort method which sorts the array (line 8). After the array has been sorted, the no-arg Sort discards the temporary array (line 9).

program44314
Program: TwoWayMergeSorter class Sort methods.

The second Sort method implements the recursive, divide-and-conquer merge sort algorithm described above. The method takes two parameters, left and right, that specify the subsequence of the array to be sorted. If the sequence to be sorted contains more than one element, the sequence is split in two (line 16), each half is recursively sorted (lines 17-18), and then two sorted halves are merged (line 19).