Anybody solved With out using heap or general 1D sorting?


#1

Anyone solved with out heap?
if(yes) pl elaborate your approach and pseudo code.

Thank you.


#2

I solved by recursion by breaking into two arrays at a time.

vector merge( vector x,vector y){

vector<int> ans;
int i=0,j=0,n=x.size(),m=y.size();
while(i<n&&j<m){
    if(x[i]<y[j]) ans.push_back(x[i++]);
    else ans.push_back(y[j++]);
    
}
while(i<n) ans.push_back(x[i++]);
 while(j<m) ans.push_back(y[j++]);
 return ans;

}

vector call(int i,int j,vector<vector > &A){
if(i==j) return A[i];
if(j-i==1){
return merge(A[i],A[j]);
}
int mid=(i+j)/2;
return merge(call(i,mid,A),call(mid+1,j,A));

}

vector Solution::solve(vector<vector > &A) {
return call(0,A.size()-1,A);
}