Sorting a File into Ascending Order

Analysis The input line will contain the path to the file to be sorted. Each element in the file will consist of a namelast name followed by a blank followed by first name followed by a blank followed by middle nameand social security number. The file is to be sorted by name; equal names should be ordered by social security number. For example, after sorting, part of the file might be as follows:

Jones Jennifer Mary 222222222

Jones Jennifer Mary 644644644

For convenience, you may assume that each name will have a middle name. Suppose the file persons.dat consists of the following:

Kiriyeva Marina Alice 333333333

Johnson Kevin Michael 555555555

Misino John Michael 444444444

Panchenko Eric Sam 888888888

Taoubina Xenia Barbara 111111111

Johnson Kevin Michael 222222222

Deusenbery Amanda May 777777777

Dunn Michael Holmes 999999999

Reiley Timothy Patrick 666666666

System Test 1:

Please enter the path for the file to be sorted.

persons.dat

The file persons.dat has been sorted. The file persons.dat will now consist of

For a larger system test, randomly generated, use the same name for each person. The social security numbers will be randomly generated ints in the range 0 ... 999999999. For example, part of the file might have

Use unit testing to increase your confidence in the correctness of your methods.

Hint: This would be a fairly simple problem if we could be certain that the entire file would fit in main memory. Unfortunately, this is not the case. Suppose we want to sort a large file of objects from the class Person. For specificity, we assume that an object in the Person class occupies 50 bytes and that the maximum storage for an array is 500,000 bytes. So the maximum size of an array of Person objects is 10,000. We start by reading in the file of persons, in blocks of k persons each. Each block is Merge Sorted and stored, in an alternating fashion, on one of two temporary files: leftTop and leftBottom. Figure 11.20 illustrates the effect of this first stage in file sorting. We then go through an alternating process which continues until all of the elements are sorted and in a single file. The temporary files used are leftTop, leftBottom, and rightBottom; personsFile itself plays the role of rightTop. At each stage, we merge a top and bottom pair of files, with the resulting double-sized blocks stored alternately on the other top and bottom pair. The code for merging sorted blocks in two files into sorted, double-sized blocks in another file is essentially what was doneusing subarrays instead of file blocksat the end of Merge Sort. Here is that code

// Merge sorted subarrays in src into dest.

for (int i = low, p = low, q = mid; i

if (q>=high ||

dest [i] = src [p++];

else

dest[i] = src[q++];

}

Figure 11.21 illustrates the first merge pass. If rightBottom is still empty after a left-to-right merge, then the sort is complete and personsFile holds the sorted file. Otherwise a right-to-left merge is performed, after which we check to see if leftBottom is still empty. If so, leftTop is copied onto personsFile and the sort is complete. How much time will this take? Suppose that we have n elements in n/k blocks, each of size k. In the Merge Sort phase, creating each of the n/k sorted blocks takes, roughly, k log2 k time, on average. Each Merge phase takes about n iterations, and there are about log2(n/k) Merge phases. The total time is the sum of the times for all phases: roughly,

(n/k) k log2k + n log2(n/k) = n log2k + n log2(n/k)

= n log2k + n log2nn log2 k

= n log2n

Because the averageTime(n) is optimal, namely linear-logarithmic in n, a sorting method such as this is often used for a system sort utility.