Java Reference
In-Depth Information
14
// splits array, sorts subarrays and merges subarrays into sorted array
15
private static void
sortArray(
int
[] data,
int
low,
int
high)
16
{
17
// test base case; size of array equals 1
18
if
((high - low) >=
1
)
// if not base case
19
{
20
int
middle1 = (low + high) /
2
;
// calculate middle of array
21
int
middle2 = middle1 +
1
;
// calculate next element over
22
23
// output split step
24
System.out.printf(
"split: %s%n"
,
25
subarrayString(data, low, high));
26
System.out.printf(
" %s%n"
,
27
subarrayString(data, low, middle1));
28
System.out.printf(
" %s%n%n"
,
29
subarrayString(data, middle2, high));
30
31
// split array in half; sort each half (recursive calls)
32
sortArray(data, low, middle1);
// first half of array
33
sortArray(data, middle2, high);
// second half of array
34
35
// merge two sorted arrays after split calls return
36
merge (data, low, middle1, middle2, high);
37
}
// end if
38
}
// end method sortArray
39
40
// merge two sorted subarrays into one sorted subarray
41
private static void
merge(
int
[] data,
int
left,
int
middle1,
42
int
middle2,
int
right)
43
{
44
int
leftIndex = left;
// index into left subarray
45
int
rightIndex = middle2;
// index into right subarray
46
int
combinedIndex = left;
// index into temporary working array
47
int
[] combined =
new
int
[data.length];
// working array
48
49
// output two subarrays before merging
50
System.out.printf(
"merge: %s%n"
,
51
subarrayString(data, left, middle1));
52
System.out.printf(
" %s%n"
,
53
subarrayString(data, middle2, right));
54
55
// merge arrays until reaching end of either
56
while
(leftIndex <= middle1 && rightIndex <= right)
57
{
58
// place smaller of two current elements into result
59
// and move to next space in arrays
60
if
(data[leftIndex] <= data[rightIndex])
61
combined[combinedIndex++] = data[leftIndex++];
62
else
63
combined[combinedIndex++] = data[rightIndex++];
64
}
65
Fig. 19.6
|
Sorting an array with merge sort. (Part 2 of 5.)
