Recurrence Relation Mergesort
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 &lt; mid and mid + 1 &lt; hi, it will be run hi-lo times if and only if a[mid - 1] &lt; a[hi] &lt; a[mid] or a[hi - 1] &lt; a[mid] &lt; 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 &lt;= hi and i &lt;= 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] &lt; a[hi] &lt; a[mid]. Otherwise, j will be increased by 1 and we will find that a[hi - 1] &lt; a[mid] &lt; 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?