代码如下:merge函数的功能为将A中[low,mid],[mid+1,high]归并成一个有序的片段。
[url=][/url]
template<class T> void merge(T A[],int low,int mid,int high){ //low to mid as the left array mid+1 to high as the right array int llen = mid-low+2; int rlen = high-mid+1; T *left = (T*)new T[llen]; T *right = (T*)new T[rlen]; //copy the low to mid to the temp array left for (int i=0;i<llen-1;i++) { left= A[low+i]; } for (i=0;i<rlen-1;i++) { right= A[mid+1+i]; } //set the sentinel left[llen-1] = numeric_limits<T>::max(); right[rlen-1]= numeric_limits<T>::max(); //merge the two array and copy to A[low,high]; int j = 0; int k = 0; for (i = low; i < high+1 ;i++) { if (left[j] < right[k]) { A= left[j]; j++; } else { A= right[k]; k++; } }
delete [] left;
delete [] right;}[url=][/url]