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.
merge()
routine is specified in page 271. $\endgroup$ – S. Sharma Apr 8 '19 at 23:38