1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – Apass.Jack Apr 8 at 10:14
  • $\begingroup$ "The number of compares is at most $n$ and no less than $\lfloor n/2\rfloor$." Where does that statement appear? $\endgroup$ – Apass.Jack Apr 8 at 10:38
  • $\begingroup$ Page 274 of the book they talk about the number of compares, and the merge() routine is specified in page 271. $\endgroup$ – S. Sharma Apr 8 at 23:38
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.