Please help me solve the following programming problem, using C, or
C++, and recursion:

We are given an array A of integers, and 6 integer parameters: lo1,
hi1, lo2, hi2, lo3, h3.

Both A[lo1 ... hi1] and A[lo2 ... hi2] are disjoint and are in
non-descending order. The procedure should merge A[lo1 ... hi1] and
A[lo2 ... hi2] into A[lo3 ... hi3] so that is in non-decreasing order.
(we must have hi3 - lo3 = hi1 - lo1 + hi2 - lo2 + 1)

Test your procedure by implementing a program which drives the
procedure. The program should invoke merge(A, 1, 25, 26, 50, 1, 50)
where A is an integer array and both A[1...25] and A[26...50] are
ordered segments of the array.

Temporary array must not be used for this purpose.

---

Request for Question Clarification by mathtalk-ga on 09 Apr 2003 06:35 PDT

Hi, tiecoon-ga:

Your specification of the problem leaves an open possibility that the
"input" ranges {lo1,..,hi1} and {lo2,..,hi2} may overlap with one
another, and also the manner in which the "output" range {lo3,..,hi3}
may overlap with either of those (a possibility realized in your
example) is unconstrained.

If one is required to use recursion without a temporary array, it
would seem to be necessary for the program to analyze these overlaps
to avoid writing over an input element before it gets used.  Consider
for example the case:

input ranges:

A[0..2] = {2,3,4}
A[2..4] = {4,5,6}

output range: A[1..6]

which corresponds to merge(A, 0, 2, 2, 4, 1, 6).

Please review the Google Answers pricing guidelines here:

http://answers.google.com/answers/pricing.html  

Even without providing working code (which seems to be the kind of
help you are asking for), the effort required to help you with this
problem is substantially more than what is usually associated with a
$5 list price.

regards, mathtalk-ga

---

Request for Question Clarification by mathtalk-ga on 09 Apr 2003 07:25 PDT

Hi, tiecoon-ga:

The "solution" posted by acdbddh-ga does not use recursion or address
the issues I've raised here about overlapping ranges.

regards, mathtalk-ga

---

Clarification of Question by tiecoon-ga on 09 Apr 2003 14:55 PDT

As A[lo1...hi1] and A[lo2...hi2] are disjoint, they cannot overlap
with one another. However, A[lo3...hi3] can overlap with them.

mojo069-ga's solution seems to solve the problem - can I award the $5
to him ?

acdbddh-ga, thank you for trying - however, as mathtalk-ga pointed
out, this solution does not use recursion.

---

Request for Question Clarification by mathtalk-ga on 09 Apr 2003 16:03 PDT

Hi, tiecoon-ga:

Thanks for clarifying that A[lo1...hi1] and A[lo2...hi2] are disjoint;
I'd overlooked that.  It remains unclear what values for lo3 and hi3
you would allow.  If you _only_ require that hi3 - lo3 = hi1 - lo1 +
hi2 - lo2 + 1, then the program given by mojo069-ga will not work on
all possible inputs.

Consider the array A[0..3] = {0,0,2,1}, and the call:

merge(A, 3, 3, 2, 2, 0, 1)

which I would expect to merge the final two entries of the array into
sorted order in the first two entries of the array.

However mojo069-ga's routine would simply return on this call, without
doing anything.  You can easily verify that each the three conditional
statements in that code will evaluate false on the conditional part:

if ( A[lo1] > A[lo2) ) ...  False, since A[3]=1, A[2]=2.

if ( lo1 < lo2 ) ... False, since lo1 = 3, lo2 = 2.

if ( lo2 < hi3 ) ... False, since lo2 = 2, hi3 = 3.

It may be that you are thinking of some restriction on the inputs to
merge( ) which obviate these concerns.  In any case you are the expert
on what answer is acceptable.  Although mojo069-ga is not a researcher
and cannot claim the price you offered for this programming question,
it is often the case that Comments made by researchers and
non-researchers alike provide helpful information.  It is always nice
to feel that one's efforts are appreciated, and I'm sure that
mojo069-ga would enjoy your acknowledgment of the effort that went
into writing that code.

If you do not wish to have any additional help with this question, you
can expire it at any time before an answer is posted.  In that case
you will not be charged the $5.00.

regards, mathtalk-ga

---

Clarification of Question by tiecoon-ga on 09 Apr 2003 16:09 PDT

Thanks mathtalk-ga,

You are right - that solution is also incomplete, but it's a good starting point.

I will expire this question as per your suggestion.

#include <stdio.h>

void Merge (int *A, int p, int q, int r)
{
  int i,j,l;
  int C;

  i=p;
  j=q+1;
  while ((i<=p)||(j<=r))
  {
    C=A[j];
    if (A[i] <= C)
    {
      i++;
    } else
      {
        for (l=j; l>=i+1; l--)
              A[l]=A[l-1];
        A[i]=C;
        i++;
        j++;
      }
  }
}


int Merge (int *A, int lo1, int hi1, int lo2, int hi2, int lo3, int
hi3)
{
  if ((lo2!=hi1+1) || (lo3!=lo1) || (hi2!=hi3))
  {
    // wrong parametrs
        return -1;
  }

  Merge(A,lo1,hi1,hi2);
  return 0;
}

int main()
{
  int i;
  int A[50]={1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,
             0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48};

  for (int i=0; i<50; i++)
    printf("%i ",A[i]);
  printf ("\n\n");

//  printf ("Merge(A,0,24,49);\n");
//  Merge(A,0,24,49);

  printf ("Merge(A,0,24,25,49,0,49);\n");
  Merge(A,0,24,25,49,0,49);

  for (int i=0; i<50; i++)
    printf("%i ",A[i]);
  printf ("\n\n");

  return 0;
}

Hi, acdbddh-ga:

You are welcome to post proposed solutions to the programming problem
here, although you appear to have posted without reading or addressing
the difficulty noted in my request for clarification above.

What you did afterwards (posting an email address and soliciting
payments) is not permitted by Google Answers' Terms of Service. 
Please review them here to avoid future infractions (see esp. Parts 2
and 4):

http://answers.google.com/answers/termsofservice.html

regards, mathtalk-ga

The solution by acdbddh-ga is not recursive.

	void merge(int A*, int low1, int high1, int low2, int high2, int
low3, int high3) {
		if (A[low1] > A[low2]) {
			A = swap(A, low1, low2);
		}
		if (low1 < low2) {
			low1++;
			merge(A, low1, high1, low2, high2, low3, high3);
		}
		if (low2 < high3) {
			low2++;
			low1 = low3;
			merge(A, low1, high1, low2, high2, low3, high3);
		}
	}
	
	void swap(int A*, int index1, int index2) {
		int tmp;
		tmp = A[index1];
		A[index1] = A[index2];
		A[index2] = tmp;
	}


	int main() {
		int A[10] = { 1, 2, 5, 7, 9, 2, 4, 6, 8, 10 };
		merge(A, 0, 4, 5, 9, 0, 9);
		for (int i = 0; i < 9; i++) {
			printf("%i ", A[i]);
		}
		return 0;
	}