Recurrence Relation Mergesort

Question

I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort:

The number of compares is at most n and no less than $\lfloor n/2 \rfloor$.

The code they gave for the merge() routine is shown below:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
{   int i = lo, j = mid+1;   
    for (int k = lo; k <= hi; k++) { 
        if (i > mid) aux[k] = a[j++];      
        else if (j > hi) aux[k] = a[i++];      
        else if (less(a[j], a[i])) aux[k] = a[j++];      
        else aux[k] = a[i++];   
    }
}

From the code, it seems that the number of compares will be at most $\lfloor n/2 \rfloor$ since if there are $n$ elements and we only compare pairs of them, there will be $\lfloor n/2 \rfloor$ compares.

Then again, I'm sure that I'm just missing something.

Thanks for any help.

Answer 1

Please trace the following code.

Integer[] a = {2, 4, 6, 8,  1, 3, 5, 7}; // an array of 8 elements.
Integer[] aux = new Integer[a.length];
merge(a, aux, 0, 3, 7);

You will find the number of compares is $7= 8-1$.

Here is a fact about general situations.

(Number of compares) Let a be an array of distinct elements. The elements from a[lo] to a[mid] is sorted increasingly. The elements from a[mid+1] to a[hi] is sorted increasingly. Then the compare less(a[j], a[i]) will be run at most hi-lo times in the call merge(a, aux, lo, mid, hi). In particular, if there is $n$ elements in a, there will be at most $n-1$ compares. If we assume lo < mid and mid + 1 < hi, it will be run hi-lo times if and only if a[mid - 1] < a[hi] < a[mid] or a[hi - 1] < a[mid] < a[hi].

Proof of "only if ": Note that after each comparison, either j is increased by 1 or i is increased by 1. The value (j-(mid+1)) + (i-lo) is increased always increased by 1.

Consider the point of time when the last comparison less(a[j], a[i]) happens. The value (j-(mid+1) + (i-lo) = hi - lo - 1. Since j <= hi and i <= mid, we must have j=hi and i = mid.

Now consider the point of time when the second last comparison happens. After that comparison, if i will be increased by 1 and we will find that a[mid - 1] < a[hi] < a[mid]. Otherwise, j will be increased by 1 and we will find that a[hi - 1] < a[mid] < a[hi].

Proof of "if" is skipped.

---

Exercise 1. What if lo = mid or mid + 1 = hi?

Exercise 2. What if there are repeated elements in a?