CareerCup

here's the deal..
u have 2 pointers each pointing to the first element of the subarrays ?
1)increment the 1st pointer as long as its value is less than ptr 2...(my idea is to keep the smaller elements in array 1 & larger ones in array 2)
2)when the above step stops(and its not the end of array 1) swap the values of ptr 1 & 2...and sort the 2nd array(it cud be done in o(n) as its almost sorted and just inserting in the rite place)
3)continue this until one of the ptrs reach te end of their subarrays...

the Worst case is O(n^2) and the best case is O(n)... any comments ?

Start merging from the end of the two arrays i.e, a[n-1] and b[m-1] and put the elements from the back of the larger array, a, i.e a[m+n-1]. This is in-place and O(m+n) time.

please ignore the previous two posts...here is the complete solution.

Suppose the arrays A, B are of size m and n respectively. For A, start at index 0 and for B start at index n-1.

while(A[i] < B[j]) {
swap(A[i], B[j];
+i;
--j;
}

After this array B will have all the lower elements(unsorted) and array A will have all the higher elements(unsorted).

now sort A and B.
Read B first to get all the lower elements in sorted order and then read A to get all the higher elements in sorted order.

Complexity O(nlogn).

If not extra space is allowed, where is the merged data placed?

It should be given that one of the two arrays has enough space for all the elements in both arrays.

Of course one of the arrays should contain enough space to accomodate both arrays. And in this case this can be done in O(n) time. Just start merging from the end and start filling elements of the resulting array from the end.

suppose we want to merge two arrays a1 and a2
a1 has n elements and has space for n + m elements
a2 has m elements
suppose arrays are sorted in ascendent order

int* merge(int* a1, int n, int* a2, int m)
{
int ind = m + n - 1; // fill resulting array from the end
--n; --m; // indexes of the last elements in arrays
while (m >= 0 && n >= 0)
{
if (a1[n] >= a2[m])
{
a1[ind] = a1[n];
--n;
}
else
{
a1[ind] = a2[m];
--m;
}
--ind;
}
if (m >= 0)
memcpy(a1, a2, (m + 1) * sizeof(int));

return a1;
}

So, the complexity of this algorithm is O(m + n)

suppose we want to merge two arrays a1 and a2
a1 has n elements and has space for n + m elements
a2 has m elements
suppose arrays are sorted in ascendent order

int* merge(int* a1, int n, int* a2, int m)
{
int ind = m + n - 1; // fill resulting array from the end
--n; --m; // indexes of the last elements in arrays
while (m >= 0 && n >= 0)
{
if (a1[n] >= a2[m])
{
a1[ind] = a1[n];
--n;
}
else
{
a1[ind] = a2[m];
--m;
}
--ind;
}
if (m >= 0)
memcpy(a1, a2, (m + 1) * sizeof(int));

return a1;
}

So, the complexity of this algorithm is O(m + n)

#include <string>
#include <iostream>
using namespace std;

int* merge(int* A, int* B, int n, int m, bool isA) {
int* cur;
if (n == 0 && m == 0)
return NULL;

if (isA)
cur = &A[n+m-1];
else
cur = &B[n+m-1];
n--;
m--;
while (n>=0 && m>=0) {
if (A[n] > B[m]) {
*cur-- = A[n--];
}
else {
*cur-- = B[m--];
}
}
while (n >= 0) {
*cur-- = A[n--];
}
while (m >= 0) {
*cur-- = B[m--];
}
return cur++;
}

int main() {
int* A, *B;
A = new int[8];
B = new int[4];
A[0] = 1;
A[1] = 4;
A[2] = 7;
A[3] = 33;
B[0] = 5;
B[1] = 6;
B[2] = 8;
B[3] = 9;
merge(A,B, 4, 4, true);
for (int i = 0; i < 8; i++)
std::cout << A[i] << ' ';
std::cout << std::endl;
}

Yeah as it is pointed having extra space makes this trivial.

If we have to arrays A and B of size m and n respectively (sorted ofcourse)
Then we have to designate A (or B) for the lower half of the values and other for the higher part of the values.

So once we decide this, we need to go ahead comparing values in A and B if we have a value higher than the corresponding index in B swap it with that value. and insert it in the right place in B. In this way we make sure that at each point while traversing up the A array we have B having an array with higher values than A[currentindex]

But the worst case would be O(n*m). if we need to do an insert for each element.

Assume two arrays A and B in ascending order.
1.
while( Scan A from begining to the end of A)
{
If A[i] is greater than B[0]
swap A[i] with B[0]
Heapify B to maintain B as a heap.
}
2.
Sort B using heapsort

3. Print out A and B

For this method, no extra space is needed and the worst case is O(nlgn).

void mergeSortedArray( int a[], int b[], int sizea, int sizeb, int result[])
{
int i,j,k;
for(i=0,j=0,k=0;i<sizea||j<sizeb;k++)
{
if((a[i]<=b[j] || j>=sizeb) && i<sizea)
{
result[k]=a[i];
i++;
}
else
{
result[k]=b[j];
j++;
)
}
}

Just doing quicksort would also give you O(nlogn). Asymptotically, it is no worse than any of the methods mentioned in this thread.

O(n) time, o(1) merging is possible, but it is really complicated and people have even written papers on it.

For O(nlogn), quicksort works, as someone pointed out.

/* 
Merger two sorted arrays into a big one
assume largeArray and smallArray are Arrays that are sorted in increasing order 
and the length of largerArray is bigger than contents in A plus the size of smallArray
the result is stored in the largerArray
*/
void merageSortedArrays(int largeArray[], int sizeA, int smallArray[], int sizeB){
    int i,j,k;
    for(i=sizeA-1,j=sizeB-1,k=sizeA+sizeB-1;i>=0 || j>=0;) {
        if(i<0) {
            largeArray[k--]=smallArray[j--];
        } else if(j<0) {
            largeArray[k--]=largeArray[i--];
        } else if(largeArray[i]>=smallArray[j]){
            largeArray[k--]=largeArray[i--];
        } else {
            largeArray[k--]=smallArray[j--];
        }
    }
}

//I have hard coded few values please ignore those.
//I think code is not complex.So reading of the code will help to understand
//Solution is O(m+n)

#include<iostream>
using namespace std;
void function(int* first,int *second,int sizeFirst,int sizeSecond)
{
int firstIndex=3;
int secondIndex=3;
while((firstIndex>=0))
{
if(first[firstIndex]<second[secondIndex])
{
first[++firstIndex]=second[secondIndex];
secondIndex--;
if(secondIndex==-1)
break;
}
else
{

first[firstIndex+secondIndex+1]=first[firstIndex];
firstIndex--;
}
}
if(secondIndex>0)
{
for(int i=0;i<=secondIndex;i++)
first[i]=second[i];
}
}
int main()
{
int first[8]={20,40,60,80};
int second[4]={1,3,5,7};
function(first,second,4,4);
}

Suppose the arrays A, B are of size m and n respectively. For A, start at index 0 and for B start at index n-1.
while(A[i] < B[j]) {
swap(A[i], B[j];
+i, --j.
}

Suppose the arrays A, B are of size m and n respectively. For A, start at index 0 and for B start at index n-1.
while(A[i] < B[j]) {
swap(A[i], B[j];
+i, --j.
}

static void merge_two_array()// BT
{
int a [] = {1,3,5,120};
int b [] = {7,8,100,110};
int temp;
int m = a.length;
int n = b.length;
for(int i=0,j=0;i<m+n;i++)
{
if(i<m)
{
if(b[j]<a[i])
{
temp = b[j];
b[j] = a[i];
a[i] = temp;
continue;
}
}
else
{
if(j < b.length-1)
{
if(b[j]>b[j+1])
{
temp = b[j];
b[j] = b[j+1];
b[j+1] = temp;
j++;
continue;
}
}
}
}
}
}

Assume that array a1 has exact more space at the end for a2 and
that both arrays are sorted.

public int[] MergeSortedArrays(int[] a1, int[] a2)
        {
            int m = a2.Length - 1;
            int n = a1.Length - 1-a2.Length;
            if (a2[0] > a1[n])
            {
                for (int i = 0; i < a2.Length; i++)
                    a1[i + 1 + n] = a2[i];
                return a1;
            }
            for (int k = 0; m >= 0 && n >= 0; k++)
            {
                if (a1[n] > a2[m])
                {
                    a1[a1.Length - 1 - k] = a1[n];
                    n--;
                }
                else
                {
                    a1[a1.Length - 1 - k] = a2[m];
                    m--;
                }
            }
            if (n < 0 && m>=0)
            {
                while (m >= 0)
                {
                    a1[m] = a2[m];
                    m--;
                }
            }
            return a1;

}

Complexy O(n) is almost possible.
Just do what "not a winner on January 19, 2009" said, but for sorting the 2nd array,
you don't need to compare from the beginning. Each time you record the insertion index for next time use. Then from this index, do a binary search to determine current insertion index.
Then, use memcpy to move elements in bulk.
The worst case is N+lgN+lg(N-1)+...=O(NlgN)

#include <stdio.h>
#include <string.h>

int main()
{
int a1[5] = {1, 2, 3, 4, 5};
int a2[10] = {2, 4, 6, 8, 10, 0};

int i = 4;
int j = 4;
int k = 9;

while((i >= 0) && (j >= 0))
{
if(a1[i] < a2[j])
{
a2[k] = a2[j];
j--;
}
else
{
a2[k] = a1[i];
i--;
}
k--;
}

while(i >= 0)
{
a2[i] = a1[i];
i--;
}

for(i=0; i<10; i++)
printf("%d\t", a2[i]);
}

#include <stdio.h>
#include <string.h>

int main()
{
int a1[5] = {1, 2, 3, 4, 5};
int a2[10] = {2, 4, 6, 8, 10, 0};

int i = 4;
int j = 4;
int k = 9;

while((i >= 0) && (j >= 0))
{
if(a1[i] < a2[j])
{
a2[k] = a2[j];
j--;
}
else
{
a2[k] = a1[i];
i--;
}
k--;
}

while(i >= 0)
{
a2[i] = a1[i];
i--;
}

for(i=0; i<10; i++)
printf("%d\t", a2[i]);
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeTwoSortedArrays
{
class Program
{
static void Main(string[] args)
{
int[] num1 = new int[10];
int[] num2 = { 40, 45, 60, 70 };
num1[7] = 30;
num1[8] = 45;
num1[9] = 65;
Print(num1);
Console.WriteLine();
Print(num2);
Console.WriteLine();
if (num1.Count() <= num2.Count())
{
num2 = Merge(num2, num1);
Print(num2);
Console.WriteLine();
Print(num1);
}
else
{
num1 = Merge(num1, num2);
Print(num1);
Console.WriteLine();
Print(num2);
}

Console.Read();

}
static void Print(int[] output)
{
for (int i = 0; i < output.Count(); i++)
{
Console.Write(output[i] + " ");
}
}
static int[] Merge(int[] big, int[] small)
{
int indexB = big.Count() - 1;
int indexS = small.Count() - 1;
int i = big.Count() - 1;// this variable will be using for while loop
int temp = 0;

while (indexS >= 0)
{
if (big[indexB] < small[indexS])
{
temp = small[indexS];
small[indexS] = big[indexB];
big[indexB] = temp;
indexB--;
}
else if (small[indexS] == 0)
{
indexS--;
i--;
indexB = i;
}
else
{
indexB--;
}
}
return big;
}
}
}

#include<stdio.h>
#include<conio.h>
void sort(int *,int, int *, int);
int main()
{
int one[]={10,33,50};
int two[]={20,45,60,55,70};
int i=3,j=5,k;

sort(one,i,two,j);

for(k=0;k<i;k++)
{printf(" %d ",one[k]);}
printf("\n");
for(k=0;k<j;k++)
{printf(" %d ",two[k]);}
getch();
}

void sort(int *a,int i, int *b, int j)
{
int x,y,min,loc,temp,p,arrstat=0;
for(x=0;x<i;x++)
{
min=a[x];
p=x;
while(p<i)
{
if(min>a[p])
{
min=a[p];
loc=p;
arrstat=0;
}
p++;
}
p=0;
while(p<j)
{
if(min>b[p])
{
min=b[p];
loc=p;
arrstat=1;
}
p++;
}
if(min!=a[x] && arrstat==0)
{
temp=a[loc];
a[loc]=a[x];
a[x]=temp;
}
else if(min!=a[x] && arrstat==1)
{
temp=b[loc];
b[loc]=a[x];
a[x]=temp;
}
}
for(x=0;x<j;x++)
{
min=b[x];
p=x;
while(p<j)
{
if(min>b[p])
{
min=b[p];loc=p;
}
p++;
}
if(min!=b[x])
{
temp=b[x];
b[x]=b[loc];
b[loc]=temp;
}
}
}

Let us assume that first 5 element is sorted in ascending order and other five is also sorted in ascending order in a single array....
#include<stdio.h>
int main()
{
int a[]={3,5,7,8,9,1,4,6,10,13};
int i=0,j=5,k=5,t=0,flag=0;

for(i=0;i<5;i++)
{
for(j=5;j<8;j++)
{
t=0;
if(a[i]>a[j])
{ //swaping
t=a[j];
a[j]=a[i];
a[i]=t;
//sorting
for(k=j;k<8;k++)
{
if(a[k]>a[k+1])
{
t=a[k];
a[k]=a[k+1];
a[k+1]=t;
}
else
{
t=0;
break;
}
}

}
else
{

break;
}
}

}
for(i=0;i<10;i++)
printf("%d,",a[i]);

getch();
}
Any comments are welcomed!!!

1.*p points to first array and *q points to second array

if(*p<*q)
{
insert_binarytree(*p);
insert_binarytree(*q);
}
else
{
insert_binarytree(*q);
insert_binarytree(*p);
}
2. perform inorder traversal in binary search tree.
inorder_traversal(root);

this will print the sorted array.

public class MergeTwoSortedArray {

    public static int[] merge(int[] a, int[] b) {

        int[] answer = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;

        while (i < a.length && j < b.length)
        {
            if (a[i] < b[j])
                answer[k++] = a[i++];

            else
                answer[k++] = b[j++];
        }

        while (i < a.length)
            answer[k++] = a[i++];


        while (j < b.length)
            answer[k++] = b[j++];

        return answer;
    }

    public static void main(String args[]){
        int[] a = {2,3,5,7,8,9,13,15,16};
        int[] b = {1,4,6,8,10,11,12,14,17,18,25,27,31};

        int[] c = merge(a,b);
        for(int i=0; i < c.length; i++){
            System.out.println("key " + i+ " :value: " + c[i]);
        }
    }
}

Create a bst traverse inorder.........................

public static void merge(int[] A, int[] B, lastA, lastB){

int indexA = A.length - 1;
int indexB = B.length - 1

while(lastB >= 0 || lastA >= 0){
if(B[lastB] >= A[lastA]){
A[indexA] = B[lastB];
indexA--;
lastB--;
}else{
A[indexA] = A[lastA];
indexA--;
lastA--;

}
}
}


I have used OR operator in the while loop. So should we still need while(lastB){
A[lastA] = B[lastB];
lastA--;
lastB--;
}

Here is the logic.
1. Use two pointers : one at the last index of 1st array and another in the first index of second array.
2. Since the arrays are sorted we can apply this logic.
a. if the one(index1) >= two(index2) then swpa this values. It is guaranteed that after merging those elements are in correct arrays.
b. stop swapping if one(index1) < two(index2).
3. Sort the final arrays in order to get merged arrays.
Overall complexity O(n log n) in place.

void MergeTwoSorted(vector<int> &one, vector<int> &two)
{
	if (one.size() == 0 || two.size() == 0)
		return;
	int I = one.size() - 1, // Last index of 1st array
		II = 0;				// first index of 2nd array
	
	/* O(n) */
	// swap the values until we bring smaller value to one array
	// and all the bigger values to second array. Since it was sorted
	// we can manipulate the array in this way.
	while ((I >= 0) && (II < two.size()-1) && (one[I] >= two[II]))
	{
		swap(one[I], two[II]);
		I --;
		II ++;
	}
	
	// At this point all the smaller values in one array and larger in another 
	/* O(Nlog N) */
	sort (one.begin(), one.end());
	sort (two.begin(), two.end());
}

Begin :
One
15 21 35 49 77 83 86 86 92 93 
Two
11 26 26 27 36 40 59 62 63 68 72 90 
End :
One
11 15 21 26 26 27 35 36 40 49 
Two
59 62 63 68 72 77 83 86 86 90 92 93

For solving the above algorithm we will use the unique method to place all the array elements in the array itself without using extra space, we will follow the step of the algorithm:
1. Put the pointer to the second last element of the first array and one pointer to the second last of the second array, then we will compare both the data if the element at first array is greater then the element of second array then, shift the array element of the first array to the index just after the element, before that store the next index element in a variable.
2. Now, we will check for the index and the condition for the element of the first array element being larger than the second array element.
3. Keep shifting all the other elements in the same way.

Implementation:

void mergesort(int arr_1[], int arr_2[], int m, int n){
	for(int i = n - 1; i >= 0; i--){
		int j;
		int last = arr_1[m - 1];
		for(j = m - 2; j >= 0 && arr_1[j] > arr_2[i]; j--)
			arr_1[j + 1] = arr_1[j];
		if(j >= 0 || last > arr_2[i]){
			arr_1[j + 1] = arr_2[i];
			arr_2[i] = last;
		}
	}
}