分治模式在每层递归时都有三个步骤:
分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
合并这些子问题的解成原问题的解。
归并排序算法完全遵循分治模式。直观上其操作如下:
分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
解决:使用归并排序递归地排序两个子序列。
合并:合并两个已排序的子序列以产生已排序的答案。
当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已排好序。
伪代码描述：
MERGE(A,p,q,r)
1n=q-p+1
2 n2=r-q
3letL[1..n+1]andR[1..n2+1]benewarrays
4fori=1ton
5L[i]=A[p+i-1]
6forj=1ton2
7R[i]=A[q+门]
8L[n+1]=∞
9R[n2+1]=∞
10i=1
11j=1
12for k=p to r
13 if L[i] <= R[j]
14 A[k]=L[i]
15 i=i+1
16else A[k]=R[i]
17j=j+1
MERGE-SORT(A,p,r)
1if p<r
2q=(p+r)/2
3MERGESORT(A,p,q)
4MERGE-SORT(A,q+1,r)
5MERGE(A,p,q,r)
Python代码：
def merge(list1,listl,listr):i,j,k=0,0,0while i < len(listl) and j < len(listr):if listl[i] <= listr[j]:list1[k] = listl[i]k+=1i+=1else:list1[k] = listr[j]k+=1j+=1#将多出的序列插入队尾while i < len(listl) :list1[k] = listl[i]k+=1i+=1while j < len(listr):list1[k] = listr[j]k+=1j+=1def mergesort(list1) :if len(list1)<2 :return list1q =int(len(list1)/2)listl= list1[:q]listr= list1[q:]#将序列分解为左右两部分，直到不能分解为止mergesort(listl)mergesort(listr)#回溯，将序列排序后合并merge(list1,listl,listr)if __name__ == '__main__':p=0r = int(input("请输入需要排序的个数"))x=input()list1 = x.split(',')list1=[int(list1[i]) for i in range(r)]mergesort(list1)print(list1)
JAVA代码：
package suanfa;import java.util.*;public class MergeSort {public static void merge(int[] A, int p, int q, int r) {int n1 =r-p+1;int[] temp = new int[n1];//没有将原数组直接分为两个数组，所以创建临时数组，用来临时存放排序后的序列int i =p;int j =q+1;int k = 0;while(i <= q && j <= r){if (A[i]<=A[j]){temp[k] = A[i];i++;k++;}else {temp[k] = A[j];j++;k++;}}while(i <= q){temp[k] =A[i];i++;k++;}while(j<= r){temp[k] =A[j];j++;k++;}for (int n =0;n<temp.length;n++){A[n+p] = temp[n];}}public static 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);}public static void main(String []args){Scanner input = new Scanner(System.in);System.out.println("请输入需要排序的数字个数：");int r = input.nextInt();int p = 0;int[] A = new int[r];for (int i = 0;i < r;i++){A[i] = input.nextInt();}mergesort(A,p,r-1);for (int i = 0;i<r;i++){System.out.printf(A[i]+" ");}System.out.printf("\n");}}
