SORTING - Introduction to Java Programming: Comprehensive Version - page 885

7 new BufferedInputStream( new FileInputStream(originalFile)));
8 DataOutputStream output = new DataOutputStream(
9

original file

new BufferedOutputStream( new FileOutputStream(f1)));

file with sorted segments

10
11 int numberOfSegments = 0 ;
12 while (input.available() > 0 ) {
13 numberOfSegments++;
14 int i = 0 ;
15 for ( ; input.available() > 0 && i < segmentSize; i++) {
16 list[i] = input.readInt();
17 }
18
19 // Sort an array list[0..i-1]
20 java.util.Arrays.sort(list, 0 , i);
21
22 // Write the array to f1.dat
23 for ( int j = 0 ; j < i; j++) {
24 output.writeInt(list[j]);
25 }
26 }
27
28 input.close();
29 output.close();
30
31

sort a segment

output to file

close file

return numberOfSegments; return # of segments

32 }

The method creates an array with the maximum size in line 5, a data input stream for the
original file in line 6, and a data output stream for a temporary file in line 8. Buffered streams
are used to improve performance.
Lines 14-17 read a segment of data from the file into the array. Line 20 sorts the array.
Lines 23-25 write the data in the array to the temporary file.
The number of segments is returned in line 31. Note that every segment has
MAX_ARRAY_SIZE number of elements except the last segment, which may have fewer
elements.

23.8.2 Implementing Phase II
In each merge step, two sorted segments are merged to form a new segment. The size of the
new segment is doubled. The number of segments is reduced by half after each merge step. A
segment is too large to be brought to an array in memory. To implement a merge step, copy
half the number of segments from the file f1.dat to a temporary file f2.dat . Then merge the
first remaining segment in f1.dat with the first segment in f2.dat into a temporary file named
f3.dat , as shown in Figure 23.19.

S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8

f1.dat

Copy to f2.dat

S 1 S 2 S 3 S 4

f2.dat

S 1 ,S 5 merged S 2 ,S 6 merged S 3 ,S 7 merged S 4 ,S 8 merged

f3.dat

F IGURE 23.19

Sorted segments are merged iteratively.