programming in C -- 2

In this lab we will write a recursive sorting algorithm called MergeSort. MergeSort is a classic example of a divide and conquer programming algorithm. The Algorithm was first described in 1945 by John von Neumann (1903-1957). Von Neumann would also be first to describe how computers could be designed to store programs. This "Von Neumann Architecture" forms the basis of most computing models today. He was also part of the Manhattan Project from 1943. In 1949 he was heard to say: "It would appear that we have reached the limits of what it is possible to achieve with computer technology, although one should be careful with such statements, as they tend to sound pretty silly in 5 years." MergeSort is an efficient sorting algorithm, but not not the fastest algorithm for sorting. One of the benefits of merge sort is it can be used for extremely large datasets that are too big to fit in memory. This was primary problem in 1945. It is still often used where the data being sorted is in removable storage(tape, disc, etc), and may exceed the ram and virtual storage of the machine performing the sort. We will be sorting using lists but the algorithm can be easily modified to sort files into files and then the actual memory requirements can be minimized. MergeSort relies on a merge operation. Where two sorted list can be merged into a larger sorted list. In the lab today we will be sorting strings which will be accomplished using strcmp. strcmp(a,b) returns zero when string a is the same as string b. When comparing strings, in C, we cannot use ==, <, or > as that will compare the pointer addresses and not the characters. strcmp(a,b) returns a negative number when a precedes b using an ascii sort (not a dictionary sort but close enough for today). strcmp(a,b) returns a positive number when a follows b in an ascii sort. (this is often implemented as the char difference: a[i]-b[i] where i is the least of the last indexes of a or b or the first different character of a and b). So string a is less than string b when strcmp(a,b) < 0 And string a is greater than string b when strcmp(a,b) > 0 And string a is equal to string b when strcmp(a,b) == 0 In the file you will be given a template for merge sort. An input and output file will be specified on the command line. You will read a the file specified on the command line (the file will contain no more than 3000 words) and sort the file using merge sort. Then write the file to the specified file location. For reference here is how merge sort might be written for integers (You can find variations in Wikipedia). Merge Sort requires some extra space during the merge operation. And a copy of the values back as well..