Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.

Code (C#):

// A1 and A2 are two sorted arrays. // A2 is not completely full (has empty slots at the end and are exactly the // size of A1) // the goal is to merge the two arrays in a sorted fashion void Merge(int[] A1, int[] A2) { int count = FindCount(A2); // get the count of full slots int i = A1.Length - 1; int j = count - 1; int k = A2.Length - 1; for(;k>=0;k--) { if(A1[i] > A2[j] || j < 0) { A2[k] =A1[i]; i--; } else { A2[k] = A2[j]; j--; } } }

i think there is a mistake in the index for smaller, it should be j instead of i.

ReplyDeletethanks for the feedback. I revised the problem description and the solution.

ReplyDeleteHave you tried running this code ? I think it will give ArrayIndexOutofBounds (or similar exception) on line:

ReplyDeleteif(A1[i] > A2[j] || j < 0)

void merge(int[] A1, int[] A2)

ReplyDelete{

int count = findCount(A2); // get the count of full slots

int i = A1.length - 1;

int j = count - 1;

int k = A2.length - 1;

for(;k>=0;k--)

{

if((i >= 0 && j >= 0 && A1[i] > A2[j]) || j < 0)

{

A2[k] =A1[i];

i--;

}

else if((i >= 0 && j >= 0 && A1[i] <= A2[j]) || i < 0)

{

A2[k] = A2[j];

j--;

}

}

}

void Merge(int[] A1, int[] A2)

ReplyDelete{

int count = FindCount(A2); // get the count of full slots

int i = A1.Length - 1;

int j = count - 1;

int k = A2.Length - 1;

for(;k>=0;k--)

{

if(A1[i] > A2[j] || j < 0)

{

A2[k] =A1[i];

i--;

if(i<0)

break;

}

else

{

A2[k] = A2[j];

j--;

}

}

}

// Both the above code doesn't work and produces invalid result. Here is the correct code and works perfectly for the above example.

ReplyDeletevoid mergeArray(int[] A1, int[] A2)

{

int count = FindCount(A2); // get the count of full slots

int i = A1.Length - 1;

int j = count - 1;

int k = A2.Length - 1;

for (; k >= 0; k--)

{

if ((i >= 0 && j >= 0 && A1[i] > A2[j]) || j < 0)

{

A2[k] = A1[i--];

}

else if ((i >= 0 && j >= 0 && A1[i] <= A2[j]))

{

A2[k] = A2[j];

A2[j--] = A1[i];

}

}

for (int l = 0; l < A2.Length; l++)

Console.WriteLine(A2[l]);

}

public int[] merge(int[] l, int[] r){

ReplyDeleteint li = 0, ri = 0, index = 0;

int[] result = new int[l.length + r.length];

while(index < (l.length + r.length)){

if(ri >= r.length || ((li < l.length) && (l[li] <= r[ri]))){

result[index] = l[li];

li++;

}else{

result[index] = r[ri];

ri++;

}

index++;

}

return result;

}