Analysis of Efficient Sorting

1. Make sure your solution for assignment 3 is working
   properly.

   See this page: http://rabbit.eng.miami.edu/class/een218/timing.html
   which shows you exactly how to make a running program time itself.

   Add the timing operation to your program, and make it tell you
   how long it took to sort the database.

   Along with the people1.txt database file from assignment 3, there
   are other database files with the same format, but of different
   sizes:
             people1.txt      1,000 entries
             people2.txt      2,000 entries
             people3.txt      3,000 entries
             people5.txt      5,000 entries
             people10.txt    10,000 entries
             people20.txt    20,000 entries
   Run your program on all 6 of those files, collect the data, and
   plot a graph: data size on horizontal axis, time on vertical axis.

   Verify that it is indeed quadratic.


2. Now make a copy of you program, and replace the sorting function.

   Implement your own merge-sort function for linked lists.

   Repeat the experiments from part 1 to produce a new graph.

   Compare the results.

   Verify that the times are as should be expected.


Turn in:

   both programs
   the raw data from the experiments
   both graphs
   both verifications (i.e. your reasoning to establish the times are correct)

as a single READABLY formatted document, preferably word.