参考答案

参考回答：

class Solution {
public:
int *sort(int *a,int lenA,int *b,int lenB){
fastSort(a,0,lenA);
fastSort(b,0,lenB);
return merge(a,lenA,b,lenB);
}
private:

//快速排序

void fastSort(int *a,int start,int end){
if(a==NULL || end-start<=1 || start<0)
return;
int pivotPos = start;
int pivot = a[start];
int temp;
for(int i=start+1;i<end;++i){
if(a[i]<pivot){
if(++pivotPos!=i){
temp = a[i];
a[i] = a[pivotPos];
a[pivotPos] = temp;
}
}
}
a[start] = a[pivotPos];
a[pivotPos] = pivot;
fastSort(a,start,pivotPos-1);
fastSort(a,pivotPos+1,end);
}

//两路归并

int *merge(int *a,int lenA,int *b,int lenB){
if(a==NULL || lenA<=0)
return b;
if(b==NULL || lenB<=0)
return a;
int *arry = new int[lenA+lenB];
if(arry==NULL){

cerr << "内存分配失败" << endl;

exit(1);
}
int posA = 0, posB = 0 ,pos = 0;
while(posA<lenA && posB<lenB){
if(a[posA]<b[posB])
arry[pos++] = a[posA++];
else
arry[pos++] = b[posB++];
}
while(posA<lenA)
arry[pos++] = a[posA++];
while(posB<lenB)
arry[pos++] = b[posB++];
return arry;
}
};