Selected solutions for HW #5


2a,b,c.  (Weiss, 7.17) Determine the running time of
mergesort for
a. sorted input
b. reverse-ordered input
c. random input

Note that for insertion sort, the answers to the
above questions would be O(N), O(N^2), and O(N^2).
So, maybe there is a "good" input for mergesort
in the same way sorted input is good for insertion
sort.

The key observation about mergesort is that no matter
what the input array looks like, mergesort will divide
the array recursively into the same subproblems.

The way the input influences the way the algorithm works
in is the merge phase of the algorithm.  A merge of
two N-element sorted arrays requires at least N
comparisons (this happens if one array's elements are
all less than the other array's smallest element)
and at most 2N-1 comparisons.  In any case, merge
requires 2N assignments.

So, merge requires Theta(N) time regardless of the input.

This implies that mergesort takes Theta(N log N) time
for sorted, reverse-sorted, and random inputs.


#3. (Weiss, 7.38) Suppose arrays A and B are both sorted
and both contain N elements.  Give an O(log N) algorithm
to find the median of A U B.


An easy O(N) time algorithm is to merge the two arrays
and take the average of the two middle elements of the
combined array.

To do this in O(log N) time, we must take advantage of
the fact that the two arrays are sorted.  Binary search
is a technique we have seen that might be able to fit
our needs here.

What do we do binary search on?  Suppose, for the sake
of simplicity, that all the elements in the two arrays
are distinct.  Now suppose we (magically) knew what
the median of A U B were.  Call it x.  Then what
we need to find is an index i such that:

B[i] < x   and A[N-i-1] > x
B[i+1] > x and A[N-i-2] < x

(Assume the arrays are indexed from 0 to N-1.)

Since we know that there are i+1 elements in B that are
less than x, then we know there needs to be N-i-1 elements
in A that are less than x.  That's essentially what the
four inequalities above are saying.

So binary search can help us find such an index.  As usual,
we let left = 0 and right = N-1.  Throughout the algorithm,
we let mid = (left + right) / 2.  (Actually, we will see
later that this is not quite right, but it is close.)

If B[mid] < A[N-mid-1], then we can eliminate indexes
left through mid-1, because for those indexes
i in [left .. mid-1], B[i+1] < x.

Similarly, if B[mid] > A[N-mid-2], we can eliminate
indexes mid through right.

After finding the right index, then we have found
the four middle elements in A U B.  To find the median,
we need to find the middle two elements of the four
and return their average.  The maximum of B[i] and A[N-i-2]
and the minimum of B[i+1] and A[N-i-1] are the two
middle elements.

There are a couple of special cases to consider:
when B[0] > A[N-1] and when A[0] > B[N-1],
but these cases are easily handled separately.

Finally, it turns out that the above algorithm works when
there are duplicate elements in the arrays.

Here is a C++ code fragment that implements the above
algorithm:

/*
   Given two sorted lists A and B,
   find the median of A U B.

*/

#include <iostream.h>

#define min(a, b) ((a < b) ? a : b)
#define max(a, b) ((a > b) ? a : b)

// Need to define what N is here

// Need to define and initialize A and B here

main()
{
  int left = 0;
  int right = N-1;
  int mid = -1;

  if (A[0] > B[N-1])
  {
    cout << "Median is " << (A[0] + B[N-1]) / 2.0 << "." << endl;
  }
  else if (A[N-1] < B[0])
  {
    cout << "Median is " << (A[N-1] + B[0]) / 2.0 << "." << endl;
  }
  else
  {
    // perform binary search to find the "crossover" index
    left = 0;
    right = N-1;
    while (left < right)
    {
      mid = (left + right + 1) / 2;
      cout << left << ", " << mid << ", " << right;
      if (B[mid] < A[N-mid-1])
      {
	cout << "  Case 1" << endl;
        left = mid;
      }
      else if (B[mid] > A[N-mid-1])
      {
	cout << "  Case 2" << endl;
        right = mid - 1;
	mid = right;  // just in case we break out of the loop next
      }
      else
      {
	cout << "  Case 3" << endl;
        break;
      }
    }

    cout << "Mid = " << mid << endl;
    // Claim: at this point,
    // B[mid] <= A[N-mid-1] and
    // B[mid+1] => A[N-mid-2]

    cout << "Median is ";
    cout << ( min(A[N-mid-1], B[mid+1]) +
	      max(A[N-mid-2], B[mid]) ) / 2.0  << "." << endl;
  }
}