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

Note
f1.dat may have one segment more than f2.dat . If so, move the last segment into
f3.dat after the merge.

Listing 23.13 gives a method that copies the first half of the segments in f1.dat to f2.dat.
Listing 23.14 gives a method that merges a pair of segments in f1.dat and f2.dat. Listing 23.15
gives a method that merges two segments.

L ISTING 23.13

Copying First Half Segments
1 private static void copyHalfToF2( int numberOfSegments,
2 int segmentSize, DataInputStream f1, DataOutputStream f2)
3 throws Exception {
4 for ( int i = 0 ; i < (numberOfSegments / 2 ) * segmentSize; i++) {
5 f2.writeInt(f1.readInt());
6 }
7 }

input stream f1
output stream f2

segments copied

L ISTING 23.14

Merging All Segments
1 private static void mergeSegments( int numberOfSegments,
2 int segmentSize, DataInputStream f1, DataInputStream f2,
3 DataOutputStream f3) throws Exception {
4 for ( int i = 0 ; i < numberOfSegments; i++) {
5 mergeTwoSegments(segmentSize, f1, f2, f3);
6 }
7
8 // If f1 has one extra segment, copy it to f3
9 while (f1.available() > 0 ) {
10 f3.writeInt(f1.readInt());
11 }
12 }

input stream f1 and f2
output stream f3

merge two segments

extra segment in f1?

L ISTING 23.15

Merging Two Segments
1 private static void mergeTwoSegments( int segmentSize,
2 DataInputStream f1, DataInputStream f2,
3 DataOutputStream f3) throws Exception {
4

input stream f1 and f2
output stream f3
read from f1
read from f2

int intFromF1 = f1.readInt();

5 int intFromF2 = f2.readInt();

6 int f1Count = 1 ;

7 int f2Count = 1 ;

8
9 while ( true ) {
10 if (intFromF1 < intFromF2) {
11 f3.writeInt(intFromF1);
12 if (f1.available() == 0 || f1Count++ >= segmentSize) {
13 f3.writeInt(intFromF2);
14

write to f3

break ;

segment in f1 finished

15 }
16 else {
17 intFromF1 = f1.readInt();
18 }
19 }
20 else {
21 f3.writeInt(intFromF2);
22 if (f2.available() == 0 || f2Count++ >= segmentSize) {
23 f3.writeInt(intFromF1);
24

write to f3

break ; segment in f2 finished

25 }