# Recurrence Relation Mergesort

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.

• "The code they gave for the merge() routine is shown below." Can you provide the actual page number or section in which that code appear? – Apass.Jack Apr 8 at 10:14
• "The number of compares is at most $n$ and no less than $\lfloor n/2\rfloor$." Where does that statement appear? – Apass.Jack Apr 8 at 10:38
• Page 274 of the book they talk about the number of compares, and the merge() routine is specified in page 271. – S. Sharma Apr 8 at 23:38

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?