Searching, Sorting and Big O - Java: How to Program Early Objects - page 832

merge: 40
47
40 47
merge: 12 26 48
40 47
12 26 40 47 48
merge: 49 56 75 85 90
12 26 40 47 48
12 26 40 47 48 49 56 75 85 90
Sorted array:
[12, 26, 40, 47, 48, 49, 56, 75, 85, 90]
Fig. 19.6 | Sorting an array with merge sort. (Part 5 of 5.)
Method mergeSort
Lines 9-12 of Fig. 19.6 declare the mergeSort method. Line 11 calls method sortArray
with 0 and data.length - 1 as the arguments—corresponding to the beginning and end-
ing indices, respectively, of the array to be sorted. These values tell method sortArray to
operate on the entire array.
Method sortArray
Recursive method sortArray (lines 15-38) performs the recursive merge sort algorithm.
Line 18 tests the base case. If the size of the array is 1 , the array is already sorted, so the
method returns immediately. If the size of the array is greater than 1 , the method splits the
array in two, recursively calls method sortArray to sort the two subarrays, then merges
them. Line 32 recursively calls method sortArray on the first half of the array, and line
33 recursively calls method sortArray on the second half. When these two method calls
return, each half of the array has been sorted. Line 36 calls method merge (lines 41-83)
on the two halves of the array to combine the two sorted arrays into one larger sorted array.
Method merge
Lines 41-83 declare method merge . Lines 56-64 in merge loop until the end of either sub-
array is reached. Line 60 tests which element at the beginning of the arrays is smaller. If
the element in the left array is smaller, line 61 places it in position in the combined array.
If the element in the right array is smaller, line 63 places it in position in the combined
array. When the while loop completes, one entire subarray has been placed in the com-
bined array, but the other subarray still contains data. Line 67 tests whether the left array
has reached the end. If so, lines 69-70 fill the combined array with the elements of the
right array. If the left array has not reached the end, then the right array must have reached
the end, and lines 73-74 fill the combined array with the elements of the left array. Finally,
lines 77-78 copy the combined array into the original array.
19.8.2 Efficiency of the Merge Sort
Merge sort is far more efficient than insertion or selection sort. Consider the first (non-
recursive) call to sortArray . This results in two recursive calls to sortArray with subarrays
each approximately half the original array's size, and a single call to merge , which requires, at
worst, n - 1 comparisons to fill the original array, which is O ( n ). (Recall that each array ele-
ment can be chosen by comparing one element from each subarray.) The two calls to sort-