**归并排序(MERGE-SORT）**是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。 归并排序动态示意图：
下面以６,５，３,１，８,７，２,４演示： 总体的步骤图： 合并步骤图：
代码实现：
import java.util.Arrays; public class MergetSort { public static void main(String[] args) { int [] arr = {6,5,3,1,8,7,2,4}; int [] temp = new int[arr.length];//归并排序需要一个额外的空间 mergetSort(arr,0,arr.length - 1,temp); System.out.println(Arrays.toString(arr)); } //分的方法 public static void mergetSort(int [] arr,int left,int right,int [] temp){ if(left < right){ int mid = (left + right)/2;//中间索引 //向左递归进行分解 mergetSort(arr,left,mid,temp); //向右递归分解 mergetSort(arr, mid + 1, right, temp); //每分解次就合并一次 merge(arr,left,mid,right,temp); } } //合并的方法 /** * * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 中转的临时数组 */ public static void merge(int []arr,int left,int mid,int right,int [] temp){ int i= left;//初始化i，左边有序序列的初始索引 int j = mid + 1;//初始化j，右边有序序列的初始索引 int t = 0;//指向temp数组的当前索引 //（一） //先把左右两边（有序）的数据按照规则填充到temp数组 //直到左右两边的有序序列，有一边处理完毕为止 while(i <= mid && j <= right){ //如果左边的有序序列的当前元素小于等于右边有序序列的当前元素 //即将左边的当前元素拷贝到temp数组，然后后移、 if(arr[i] <= arr[j]){ temp[t] = arr[i]; t += 1; i += 1; }else{//反之将右边的有序序列的当前元素拷贝到temp数组 temp[t] = arr[j]; t += 1; j += 1; } } //（二） //把有剩余数据的一遍的数据依次全部填充到temp while(i <= mid){//说明左边的有序序列有剩余，全部填充到temp temp[t] = arr[i]; t += 1; i += 1; } while(j <= right){//说明右边的有序序列有剩余，全部填充到temp temp[t] = arr[j]; t += 1; j += 1; } //（三） //将temp数组的元素拷贝到arr,注意，并不是每次都是拷贝所有 t = 0; int leftTemp = left; while (leftTemp <= right){ arr[leftTemp] = temp[t]; t += 1; leftTemp += 1; } } }