Computer Science 269
Introduction to Data Structures
Spring 2000
Assignment 4 and 5 Hints for Mergesort
Due Friday, March 3, and Friday, March 10, 2000.

Any sorting algorithm whose fundamental action is to merge
sorted lists, starting with smaller lists and ending with the a sorted list
containing all the original items, can be called mergesort.
Array Implementation.
The simplest form of mergesort uses arrays. If the size of the array is
less than some small number just use selectionsort. Otherwise, copy the
array into two auxiliary arrays each half the size. Recursively, sort
each of the auxiliary arrays. Then merge those back forming a sorted
array containing all the orginal items.
Linked List Implementation.
An alternative is to use linked lists. In that case, items do not need
to be copied. Only pointers need to be redefined, so no new dynamic
memory is needed for the algorithm.
Polyphase Mergesort.
Polyphase mergesort is based on a somewhat different idea. We define a
run to be a maximal sorted sublist. For example, the list of
items {3,5,9,2,7,10,6} consists of 3 runs.
The basic idea of polyphase mergesort is to decrease the number of runs
at every iteration of the main loop by merging runs in pairs. Eventually,
there will be just one run, which implies that the items are sorted.
There are at any time up to four lists of items. During each iteration
of the loop, two of those lists, which we call A and B, are read,
and two lists, which we call C and D, are written.
In the last iteration, only one list is written, and that is the final
sorted list.
The initial step is to divide the items into two lists, each of which has
at most n/2 runs.
At the beginning of each iteration of the main loop, there are two lists,
which we call A and B. Each of them consists of a number of runs.
Within each iteration of the main loop, there is an inner loop. Each
iteration of the inner loop merges one run of A and one run of B, creating
just one run, which is written to either C or D. We alternate writing to
C and D so that they will contain equal (or nearly equal) numbers of runs.
If A has more runs than B, the extra runs of A are simply copied to C and D.
(Likewise if B has more runs than A.)
At the end of one iteration of the main loop, A and B are deleted and
C and D are renamed A and B.
The total number of runs is approximately halved at each iteration of the
main loop, except possibly for the first iteration.
Eventually there will be just one run in C, and it will contain the
entire set of items in sorted order.
External Polyphase Mergesort.
Polyphase mergesort is ideal for merging files that are far too large to
be brought into main memory. The lists A and B are simply maintained
as input streams and C and D as output streams. And the end of each
iteration, the input files are deleted, and the output files are closed
and then reopened as input files, The amount of additional memory needed
is small.
Each iteration of the main loop requires reading and writing every item.
Since i/o operations are slow, it is desirable to minimize them.
One technique is to initially read the items into the main memory in
large blocks (as large as possible, given the capacity of the memory),
then sort those blocks using some other algorithm, and then write them
out as a run to an output stream. The number of runs in the resulting
output stream will be roughly n divided by the memory size of
the computer. The number of iterations of the main loop saved by this
method is roughly the base 2 logarithm of the memory size.
Eliminating Duplicates.
Mergesort is ideal for eliminating duplicate items, if that is desired.
The duplicates are eliminated at the time two lists are merged into one.
This can be done using any of the variations discussed above.
However, for Assignments 4 and 5, do not eliminate duplicate items.
