Java实现的归并排序算法

归并排序算法基本思想：

将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

 

Java源代码如下：

public class MergeSort {
	
	private static void mSort(int[] arr, int[] temp, int m, int n) {
		if (m == n) return;  
        int mid = (m+n)/2;  
        mSort(arr, temp, m, mid);  
        mSort(arr, temp, mid+1, n);  
        for (int i = m; i <= n; i++) {  
            temp[i] = arr[i];  
        }  
        int index1 = m;  
        int index2 = mid + 1;  
        int index = m;  
          
        while (index1 <= mid && index2 <= n) {  
            if (temp[index1] < temp[index2]) {  
                arr[index++] = temp[index1++];  
            } else {  
                arr[index++] = temp[index2++];  
            }  
        }  
        while(index1 <= mid) {  
            arr[index++] = temp[index1++];  
        }  
        while(index2 <= n) {  
            arr[index++] = temp[index2++];  
        }  
	}
	
	public static void mergeSort(int arr[]) {  
		int temp[] = new int[arr.length];  
        mSort(arr,temp,0,arr.length-1);
    }  
  
	public static void main(String[] args) {
		int[] data = new int[]{4,3,2,5,3,6,4,2};
		mergeSort(data);
		for(int i = 0; i < data.length; i ++) {
			System.out.println(data[i]);
		}
	}
}