Merge-sort (4)
Analysis (counting comparisons):
Let n = right–left+1 be the length of the array.Let the total no. of comparisons required to sort n values be comps(n).
The left subarray’s length is about n/2, so step 1.2 takes about comps(n/2) comparisons to sort it.
Similarly, step 1.3 takes about comps(n/2) comparisons to sort the right subarray.
Step 1.4 takes about n–1 comparisons to merge the subarrays.