Java Reference
In-Depth Information
while
( (beginHalf1 <= endHalf1)
and
(beginHalf2 <= endHalf2) )
{
if
(a[beginHalf1] <= a[beginHalf2])
{
tempArray[index] = a[beginHalf1]
beginHalf1++
}
else
{
tempArray[index] = a[beginHalf2]
beginHalf2++
}
index++
}
//
Assertion: One subarray has been completely copied to
tempArray
.
Copy remaining entries from other subarray to
tempArray
Copy entries from
tempArray
to array
a
9.4
Tracing the steps in the algorithm.
Let's examine what happens when we invoke
mergeSort
on the
array halves. Figure 9-3 shows that
mergeSort
divides an array into two halves and then recursively
divides each of those halves into two halves until each half contains only one entry. At this point in the
algorithm, the merge steps begin. Pairs of one-entry subarrays are merged to form a two-entry subarray.
Pairs of two-entry subarrays are merged to form a four-entry subarray, and so on.
FIGURE 9-3
The effect of the recursive calls and the merges during a merge sort
7
5
9
6
0
2
3
4
1
11
0
Effect of
recursive
calls to
mergeSort
7
5
9
3
6
2
4
2
6
12
16
7
9
3
6
5
0
2
4
3
4
7
8
13
14
17
18
7
5
9
3
6
0
2
4
15
19
5
9
5
7
3
9
0
6
2
4
10
20
Merge steps
3
5
7
9
0
2
4
6
21
0
3
4
6
7
9
2
5
Copy to
original array
0
2
3
4
5
6
7
9
Numbers on the arrows in the figure indicate the order in which the recursive calls and the
merges occur. Notice that the first merge occurs after four recursive calls to
mergeSort
and before
other recursive calls to
mergeSort
. Thus, the recursive calls to
mergeSort
are interwoven with calls
to
merge
. The actual sorting takes place during the merge steps and not during the recursive calls.
