???? 分治法，顧名思義：切分然后治理，治理就是各個解決問題然后合并整理。遞歸的解決分成n個較小規模的子問題，然后將各個結果合并從而解決原來的問題。
DIVIDE：將問題分解成一系列子問題。
CONQUER：遞歸地解決各個子問題，若問題足夠小，則直接解決。
COMBINE：將子問題的結果合并成原問題的解。
自己編的代碼，結果又運行不起來：ps:幾經修改，看來細節問題要注意，簡化推理是個好辦法
//mergesort
#include<iostream>
using namespace std;

int merge(int*A,int p,int q,int r){
?int n1=q-p+1;
?int n2=r-q;
?int* L = new int[n1];
?int* R = new int[n2];
?for(int i=0;i<n1;++i)
? L[i]=A[p+i];
?for(int j=0;j<n2;++j)
? R[j]=A[q+1+j];
?i=0;j=0;
?for(int k=p;k<r;k++){
? if(L[i]<=R[j]){A[k]=L[i++];}
? else {A[k]=R[j++];}
?}
?return(0);
}

int mergesort(int*A,int p,int r){
?int q;
?if(p<r){
? q=(p+r)/2;
? mergesort(A,p,q);
? mergesort(A,q+1,r);
? merge(A,p,q,r);
?}
?return(0);
}

int main(){
??? int b[6]={11,65,53,78,38,63};
??? mergesort(b,0,5);
?for(int i=0;i<6;++i)
? cout<<b[i]<<'\t';
?return(0);
}

以下引用自：gooler的專欄http://blog.csdn.net/Gooler/archive/2006/03/22/632422.aspx有各種排序算法quicksort,heapsort...
/*
?* A is an array and p, q, and r are indices numbering elements of the array
?* such that p <= q < r.
?*
?* This procedure assumes that the subarrays A[p. .q] and A[q + 1. .r] are in
?* sorted order. It merges them to form a single sorted subarray that replaces
?* the current subarray A[p. .r].
?*/
void merge(int A[], int p, int q, int r) {
??? int i, j, k, size;
??? int* B;
???
??? size = r - p + 1;

??? B = new int[size]; /* temp arry for storing the merge result */
???
??? /* initialize B */
??? for (i = 0; i < size; ++i) {
??? ??? B[i] = 0;
??? }

??? i = p;
??? j = q + 1;
??? k = 0;
???
??? /* compare and copy the smaller to B */
??? while (i <= q && j <= r) {
??? ??? if (A[i] < A[j]) {
??? ??? ??? B[k++] = A[i++];
??? ??? } else {
??? ??? ??? B[k++] = A[j++];
??? ??? }
??? }
???
??? /* copy the rest to B */
??? while (i <= q) {
??? ??? B[k++] = A[i++];
??? }???
??? while (j <= r) {
??? ??? B[k++] = A[j++];
??? }
???
??? /* replace A[p..r] with B[0..r-p] */
??? for (i = p, k = 0; i <= r; ++i, ++k) {
??? ??? A[i] = B[k];
??? }

??? delete[] B;
}

/*
?* This procedure sorts the elements in the subarray A[p. .r].
?*
?* If p >= r, the subarray has at most one element and is therefore
?* already sorted. Otherwise, the divide step simply computes an index
?* q that partitions A[p. .r] into two subarrays: A[p. .q], containing n/2
?* elements, and A[q + 1. .r], containing n/2 elements.
?*/
void mergeSort(int A[], int p, int r) {
??? if (p >= r) return;
???
??? int q = (p + r) / 2;
???
??? mergeSort(A, p, q);
??? mergeSort(A, q + 1, r);
??? merge(A, p, q, r);
}