it can be done in O(m) . Use something like binary search . code is here .......
#include<stdio.h> void splitMN(int a[],int m , int b[], int n){ int al = 0 , bl = 0 ; int ah = m-1 , bh = n-1 ; int ai = (ah+al+1)/2; int bi = (bh+bl+1)/2; while(ai+bi!=m){ printf("Enter ai = %d, bi = %d\n ",ai,bi); if(ai+bi < m){ if(a[ai] < b[bi]){ al = ai ; if(al == ai) break; ai = (ah+al+1)/2; }else{ bl = bi ; if(bh == bi) break; bi = (bh+bl+1)/2; } }else{ if(a[ai] > b[bi]){ ah = ai ; if(ah == ai) break; ai = (ah+al+1)/2; }else{ bh = bi ; if(bh == bi) break; bi = (bh+bl+1)/2; } } } bi = 0 ; ai ; while(ai < m){ a[ai] = a[ai]^b[bi]^(b[bi] = a[ai]); ai++ ; bi++ ; } } int main(){ int m , n ; printf("Enter m , n : "); scanf("%d%d",&m,&n); int a[m] , b[n] ; int i ; for(i = 0 ; i< m ; i++) scanf("%d",&a[i]); for(i = 0 ; i< n ; i++) scanf("%d",&b[i]); printf("Enter m , n : "); splitMN(a,m,b,n); for(i = 0 ; i< m ; i++) printf("%d\t",a[i]); printf("\n"); for(i = 0 ; i< n ; i++) printf("%d\t",b[i]); printf("\n"); } On Sat, Jun 4, 2011 at 4:03 AM, Aakash Johari <aakashj....@gmail.com> wrote: > Please try this solution. And tell if it fails at any case. If it works > fine, I will tell the logic. > > >> #include <stdio.h> >> #include <stdlib.h> >> >> void merge(int *a, int m, int *b, int n) >> { >> int i, j, k; >> int t; >> >> i = j = 0; >> k = -1; >> >> while ( i < m && a[i] < b[j] ) { >> i++; >> } >> >> while ( i < m && j < n ) { >> if ( k == -1 && b[j] < a[i] ) { >> t = a[i]; a[i] = b[j]; b[j] = t; >> k = j; >> j++; >> i++; >> } else if ( b[j] < b[k] ) { >> t = a[i]; a[i] = b[j]; b[j] = t; >> j++; >> i++; >> } else { >> t = a[i]; a[i] = b[k]; b[k] = t; >> i++; >> } >> } >> } >> >> int main() >> { >> int m, n; >> int *a, *b; >> int i; >> >> scanf ("%d%d", &m, &n); >> >> a = (int*) malloc(sizeof(int) * m); >> b = (int*) malloc(sizeof(int) * n); >> >> for ( i = 0; i < m; i++ ) >> scanf ("%d", a + i); >> >> for ( i = 0; i < n; i++ ) >> scanf ("%d", b + i); >> >> merge (a, m, b, n); >> >> printf ("After Merge Operation : \n"); >> >> printf ("1st Array : "); >> >> for ( i = 0; i < m; i++ ) { >> printf ("%d ", a[i]); >> } >> >> printf ("\n2nd Array : " ); >> >> for ( i = 0; i < n; i++ ) { >> printf ("%d ", b[i]); >> } >> >> return 0; >> } >> >> >> On Fri, Jun 3, 2011 at 8:07 AM, bittu <shashank7andr...@gmail.com> wrote: > >> @sravanreddy...logical bugs if A is size of n & B is size m from your >> example assuming n<m so if you want smallest m elements in A then u >> only capacity of n elements & didn't allocate memory so these elements >> initialized by INT_MIN for m-n nodes so that array A can hold m >> smallest elements then what r u swapping u dude..isn't garbage >> value ?? you will get at 1st step only just run it ?? in you algo >> A_End=m-1(which 4th position in Array that DNE)..?? & also you have to >> free memory for m-n in array B as it contains n largest elements . >> >> take >> A= 1,2,3 n=3 >> B= 0,1,4,5,9 m=5 >> >> after allocating memory to Array A for m-n elements A will looks >> likes 1 2 3 INT_Max INT_Max >> now what you wants A should contains m smallest elements & B have n >> largest elements >> so O/P should be A=1,2,3,1,0 & B=INT_Max,INT_Max,4,5,9 now free >> memory used by 1st elements in array B so that A will represent M >> smallest elements & B will have n Largest elements >> >> so that above will work. >> >> Hope I am Correct let me know if any issue with explanation >> >> Thanks >> Shashank>>"The Best Way To Escape From The problem is To Solve It" >> CSE,BIT Mesra >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > -Aakash Johari > (IIIT Allahabad) > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *With Regards :* Ravinder Kumar B.Tech 3rd Year Computer Science and Engineering MNNIT Allahabad -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.