Binary Tree Database

The database files that you used for one of the introduction to programming
labs are coming back again. They all follow this format:

114680858 07061967 Matilda Vincent MI 6050.75
114930037 24101947 Desdemona Hanover ID 2440.47
115550206 10011979 Xanadu Perlman ND 14997.39
116520629 21091963 Alexander Hall SD 756.15
117050976 16101930 David Lamprey GA 142.60
119610646 02021965 Thomas Porlock IL 383.11
120330928 26111962 Cary Cartman NC 9813.81
122460462 11041962 Bella Oldman SD 3186.90
123040628 13021922 Elizabeth Watson NC 18971.91
123580905 08031923 Gustav Hornswaggle MN 4852.70
125040813 13061984 Godfrey Tumor OR 16760.20
125610677 03091958 Gustav Trentham IA 89.12
126470499 19121952 Justin Oddly MA 66038.10

One person per line, and for each person we are given six things - social 
security number, date of birth, first name, last name, state of residence,
and bank balance.

The birth date format is slightly different this semester. Instead of the
usual YYYYMMDD, it has been switched around to DDMMYYYY, so Justin Oddly's
19121952 means the 19th of December 1952.

This URL gives you access to 9 different data files. Same format, different
lengths:
          http://rabbit.eng.miami.edu/class/een118/labs/161/
if you are working on rabbit, you don't need to download the files into
your own directory, you can access them directly like this:
          f.open("/home/www/class/een118/labs/161/data1.txt");

+ Define a person object to hold all the data for one person.

+ Read all the data from a database file into an array of pointers to person
  objects.

+ Mergesort the array alphabetically on names:
     Sort primarily on last name,
     when two last names are the same, use first names,
     if both names are the same, use state, birthdate, or whatever, your choice.

+ Make sure that it is correctly sorted!

+ Veryify that you really have got an NlogN implementation.
  That means run it on files of different lengths, measure how long it takes,
  and do some simple calculations.


Here is a timing function you can use on rabbit.
Call it once just before sorting, and again immediately after. The difference is
the number of seconds it took.

#include <time.h>
#include <sys/resource.h>

double get_cpu_time()
{ struct rusage ruse;
  getrusage(RUSAGE_SELF, &ruse);
  return ruse.ru_utime.tv_sec+ruse.ru_utime.tv_usec/1000000.0 + 
         ruse.ru_stime.tv_sec+ruse.ru_stime.tv_usec/1000000.0; }