Java Reference
In-Depth Information
3.
Consider the following implementation of an iterative merge sort. Scan the array from its beginning and partition
it into segments that are each sorted. As you find each segment, represent it as a pair of indices and place the pair
at the end of an initially empty vector.
Next, remove the first two pairs from the vector and merge the array segments they represent. Notice that
these segments are adjacent in the array. The merge results in a larger segment that is sorted. Place the pair of indi-
ces that represents the resulting segment at the end of the vector. Repeat the steps in this paragraph until only one
entry remains in the vector.
Sometimes during the process, the two pairs at the beginning of the vector will represent segments that are
not adjacent. In this case, move the first pair to the end of the vector and continue.
a.
What is the best-case performance of this algorithm?
b.
What is the worst-case performance of this algorithm?
c.
Implement the algorithm.
FIGURE 9-13
Special cases in an iterative merge sort after merging one-entry subarrays
(a)
7
5
9
3
6
0
2
7
5
9
3
6
0
2
5
7
3
9
0
6
3
5
7
9
0
2
6
0
2
3
5
6
7
9
(b)
7
5
9
3
6
0
7
5
9
3
6
0
5
7
3
9
0
6
3
5
7
9
0
3
5
6
7
9
(c)
7
5
9
3
6
7
5
9
3
6
5
7
3
9
3
5
7
9
3
5
6
7
9
