// Merge Sort #include using namespace std; template void twoway(T* a, T* b, int na, int nb){ // a[ ]: left sorted array, and resulting sorted array // b[ ]: right sorted array // na: size of a[ ] // nb: size of b[ ] T c[na+nb]; // temp resulting array int iLeft = 0; // index for left sorted array int iRight = 0; // index for right sorted array int iMerge = 0; // index for temp array while( iLeft < na && iRight < nb){ if(a[iLeft] <= b[iRight]){ c[iMerge] = a[iLeft]; ++iLeft; ++iMerge; }else{ c[iMerge] = b[iRight]; ++iRight; ++iMerge; } } // if there are remaining in left array while(iLeft < na){ c[iMerge] = a[iLeft]; ++iLeft; ++iMerge; } // if there are remaining in right array while(iRight < nb){ c[iMerge] = b[iRight]; ++iRight; ++iMerge; } // copy temp resulting array into a[ ] for(int i=0 ; i < na+nb ; ++i){ a[i] = c[i]; } } // recursive merge sort template void MergeSort(T* a, int left, int right){ if(left < right){ int mid = (left + right)/2; MergeSort(a,left,mid); MergeSort(a,mid+1,right); twoway(a+left, a+mid+1, mid-left+1, right-mid); } } int main(){ int unsorted[10] = {5,3,8,6,2,7,1,4,10,9}; // print unsorted array for(int i=0 ; i < 10 ; ++i) cout << unsorted[i] << " "; cout << endl; MergeSort(unsorted,0,9); // print sorted array for(int i=0 ; i < 10 ; ++i) cout << unsorted[i] << " "; cout << endl; return 0; } //---------------------------------------- void twoway(int a[ ], int b[ ], int c[ ], int na, int nb) /* a[ ] and b[ ] are input sorted arrays */ /* c[ ] is the output sorted array after a[ ] and b[ ] are merged */ /* na and nb are the lengths of a[ ] and b[ ], respectively */ int merge_sort(int a[], int left, int right){ // sorting between left and right if(left < right){ int mid = (left + right)/2; // or left + (right - left)/2; merge_sort(a, left, mid); merge_sort(a, mid+1, right); int c[right - left + 1]; // or int *c = new int[right-left+1]; twoway(a+left, a+mid+1, c, mid-left+1, right-mid); for(int i=0 ; i < right - left + 1 ; ++i) // This step is needed; otherwise, array a[ ] remains unsorted, // since the sorted result is stored in c[ ] a[i + left] = c[i]; } return 1; // end of conquer } // ---------------------------------or----------------------------- int merge_sort(int a[], int n){ // n is the length of a[ ] if(n==1) return 1; // stop dividing merge_sort(a, n/2); merge_sort(a + n/2, n - n/2); int c[n]; // or int *c = new int[n]; twoway(a, a + n/2, c, n/2, n - n/2); for(int i=0 ; i < n ; ++i) // This step is needed; otherwise, array a[ ] remains unsorted, // since the sorted result is stored in c[ ] a[i] = c[i]; return 1; // end of conquer }