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

int values are sorted. They are denoted as S 1 , S 2 , c , and S k , where the last segment,
S k , may contain less than 100000 values.

Original file

Program

Unsorted

Array

Temporary file

Sorted
segment

Sorted
segment

Sorted
segment

……

S 1 S 2 S k

F IGURE 23.17

The original file is sorted in segments.

Phase II: Merge a pair of sorted segments (e.g., S 1 with S 2 , S 3 with S 4 , c , and so on)
into a larger sorted segment and save the new segment into a new temporary file. Continue
the same process until only one sorted segment results. Figure 23.18 shows how to merge
eight segments.

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

Merge step

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

Merge step

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

Merge step

Final sorted
segment

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

F IGURE 23.18

Sorted segments are merged iteratively.

Note
It is not necessary to merge two successive segments. For example, you can merge S 1
with S 5 , S 2 with S 6 , S 3 with S 7 and S 4 with S 8 , in the first merge step. This observation is
useful in implementing Phase II efficiently.

23.8.1 Implementing Phase I
Listing 23.12 gives the method that reads each segment of data from a file, sorts the segment,
and stores the sorted segments into a new file. The method returns the number of segments.

L ISTING 23.12

Creating Initial Sorted Segments
1 /** Sort original file into sorted segments */
2 private static int initializeSegments
3 ( int segmentSize, String originalFile, String f1)
4 throws Exception {
5 int [] list = new int [segmentSize];
6 DataInputStream input = new DataInputStream(