归并排序Java实现

public class MergeSort {

    public static void sort(int[] a,int left, int right){
        if(left >= right) return;
        int center = (left + right) >> 1;
        sort(a, left, center);
        sort(a, center + 1, right);
        merge(a, left, center, right);
    }
    public static void merge(int[] data, int left, int center, int right){
        int [] tmpArr = new int[right + 1]; //辅助数组
        int mid = center + 1;
        int index = left;
        int tmp = left;

        while(left <= center && mid <= right){ //左右比较将较小的加入到临时数组
            tmpArr[index++] = (data[left] <= data[mid]) ? data[left++] : data[mid++];
        }
        // 将剩余的尾部数据加入到临时数组
        while(left <= center){
            tmpArr[index++] = data[left++];
        }
        while(mid <= right){
            tmpArr[index++] = data[mid++];
        }
        // 将临时数组中的数据加入到原数组中
        for(int i=tmp; i<= right; i++)
            data[i] = tmpArr[i];
		/* 展示递归效果
		for(int b : data)
            System.out.print(b+" ");
        System.out.println();
		*/ 
    }
    //测试程序
    public static void main(String[] args) {
	    int[] a = {49, 38, 65, 97, 76, 13, 27, 50};
	    sort(a, 0, a.length -1 );
	    for(int b : a)
            System.out.print(b+" ");
    }
}

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