归并排序的核心思想是分治策略，把原问题分解为规模更小的子问题求解，然后再把求解后的子问题的解合并为原问题的解。
废话不多说，直接看代码：
package com.zjq.arithmetic.sort; public class Merge_Sort { public static void main(String[] args) { int[] input={4,3,2,1,6,7,9,8,56,34,12}; Merge_Sort m=new Merge_Sort(); int[] result=m.merge_sort(input, 0, input.length-1); for(int i=0;i<input.length;i++){ System.out.println(result[i]); } } /** * 排序方法 * @param input 输入数组 * @param start 数组开始下标 * @param end 数组结束下标 * @return */ private int[] merge_sort(int[] input,int start,int end){ if(start<end){ int mid=(start+end)/2; merge_sort(input,start,mid); merge_sort(input,mid+1,end); merge(input,start,mid,end); } return input; } /** * 把下标为start至mid 和 mid+1至end的两个排序好的数组部分，合并到原数组中。 * @param input 输入数组 * @param start 开始下标 * @param mid 结束下标 * @param end */ private void merge(int[] input,int start,int mid,int end){ int k=start; int l=mid+1; int[] tempA=new int[end-start+1]; int m=0; //依次比较两个数组部分的首元素 while(k<=mid&&l<=end){ if(input[k]<input[l]){ tempA[m]=input[k]; k++; }else{ tempA[m]=input[l]; l++; } m++; } //剩余部分加入到末尾 while(k<=mid){ tempA[m]=input[k]; m++; k++; } //剩余部分加入到末尾 while(l<=end){ tempA[m]=input[l]; m++; l++; } for(int i=start,j=0;i<=end;i++,j++){ input[i]=tempA[j]; } } }