归并排序的思想：

与快排的思想很相似归并排序也是采用分治的方法，不过归并与快排的顺序是相反的，归并排序需要先划分区间，以mid = l + r >> 1, 为中间点划分出两个区间对两个区间进行排序，然后再将这两个有序的区间合并成一个有序的区间。也就是说快排是从大区间一路操作到小区间，而归并是从小区间一路操作到大区间。

归并排序中最重要、最难的一步是如何合并两个有序的区间。那么这一步也是通过两个指针i,j来实现
当我们拥有两个区间[l, mid] ， [mid + 1, r]时，我们让两个指针同时指向两个区间的首端，即i = l, j = mid + 1。我们每次比较q[i] 与 q[j] 的大小，将最小的取出，取出的方法我们采用另一个数组temp[]储存，设k为存入的个数，则每次取出的操作就是temp[k++] = q[i] ( 或q[j]) )。当其中一个指针已经走完整个区间的时候，因为两个区间都是有序的，所以可以直接将另一个区间指针后面的数插入到temp[]后面。

代码模板

c++：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>

using namespace std;

const int N=100010;

int q[N];

int temp[N];

int n;




void mergeSort(int q[],int l,int r){
	
	if(l>=r)  return;
	
	int mid=l+r>>1;
	
	mergeSort(q,l,mid),mergeSort(q,mid+1,r);
	
	int k=0,i=l,j=mid+1;
//	把一个分割好的数组分成左右俩个区间，取得中间值当分界点
 
	while(i<=mid&&j<=r)
//		 双指针开始比较哪一个指针指向的数字更小，然后放temp数组里面
		if(q[i]<=q[j]) temp[k++]=q[i++];
		else 		   temp[k++]=q[j++];
	
		while(i<=mid) temp[k++]=q[i++];
		while(j<=r)   temp[k++]=q[j++];
//		最后把temp数组里面的数放到q数组里面 
		for(i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
		
}


int main(){
 	scanf("%d",&n) ;
 	
 	for(int i=0;i<n;i++) scanf("%d",&q[i]); 
 	
	mergeSort(q,0,n-1);
	
 	for(int i=0;i<n;i++) printf("%d",q[i]); 
	
	return 0;
}

java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 import java.io.*;

class Main{
    static int N=100010;
    static int[] a=new int[N];
    static void merge_sort(int[] nums,int l,int r){
        if(l >= r) return;//如果超出界限
        int mid=l+r>>1;//找到分界点
        merge_sort(nums,l,mid);//开始递归
        merge_sort(nums,mid+1,r);
        int[] temp=new int[r-l+1];//合并的那个数组
        int k=0;//合并数组的那个指针
        int i=l;//左数组的i
        int j=mid+1;//右数组的mid+1
        while(i<=mid&&j<=r){
            if(nums[i]<=nums[j]) temp[k++] = nums[i++];//合并数组中存放的是最小的
            else  temp[k++] = nums[j++];
        }

        while(i<=mid)  temp[k++] = nums[i++];//左侧小集合还有剩余，依次放入大集合尾部
        while(j<=r)  temp[k++] = nums[j++];//右侧小集合还有剩余，依次放入大集合尾部

        for(i= l, j = 0 ; i <= r ; i++ , j++){//合并操作 i 从left起
            num[i] = temp[j];
        }
    }

    public static void main(String[]args)throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(in.readLine());

        String[]arr=in.readLine().split(" ");
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(arr[i]);

        merge_sort(a,0,n-1);
        for(int i=0;i<n;i++) System.out.print(a[i]+" ");
    }
}