Java™ How To Program (Early Objects), Tenth Edition

Section 19.8 Merge Sort

• Merge sort (p. 827) is a sorting algorithm that’s faster, but more complex to implement, than selection sort and insertion sort. The merge sort algorithm sorts an array by splitting it into two equalsized subarrays, sorting each subarray recursively and merging the subarrays into one larger array.

• Merge sort’s base case is an array with one element. A one-element array is already sorted, so merge sort immediately returns when it’s called with a one-element array. The merge part of merge sort takes two sorted arrays and combines them into one larger sorted array.

• Merge sort performs the merge by looking at the first element in each array, which is also the smallest element in the array. Merge sort takes the smallest ...