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

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 element can be chosen by comparing one element from each subarray.) The two calls to sortArray result in four more recursive sortArray calls, each with a subarray approximately a quarter of the original array’s size, along with two calls to merge that each require, at worst, n/2 – 1 comparisons, for a total number of comparisons of O(n). ...