- Your program should read the input files by using Unix shell redirection (e.g. a.out<lab1.dat) to read the input from
stdin (C). By using redirection, it is unnecessary to open and close the input file, nor should your program prompt for a
file name. You should dynamically allocate tables for storing the input and the table of links. Unlike the mergesort in
Notes 1 and CLRS, the keys are never copied.
- The link values are not initialized before the recursive mergesort begins. Each link will be initialized to -1 when its
sequence value is placed in a single-element list (at the bottom of the recursion’s “tree”).
- The input sequence array and the link array may be global. Under this assumption, the following prototype may be used:
int mergeSort(int start,int count)
where start is the first subscript for a subarray of count elements. The returned int is the subscript of the first
element in the resulting sorted sublist. The last element in the sublist will have a link value of -1.
- The critical part of the code is a merge of two subarrays that previously had their link values set for ordered sublists. The
merge will revise the link values to give a single ordered list.
- If an input value appears more than once, those elements should be ordered by subscripts in the final list, i.e. your sort
code will be stable.
- Consider the following input file:
The output will be:
First element is at subscript 4
0 3 5
1 5 2
2 6 3
3 7 -1
4 0 6
5 4 1
6 1 7
7 2 0
Notice that the input sequence ordering has not changed