1、概述

排序就是将一组对象按照某种逻辑顺序重新排列的过程。

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序基本思想：

（1）将待排序数组分为分为两部分，i 和j分别指向待排序子序列的第一个元素，比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]（申请的临时数组，大小为子序列之和）中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

（2）归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

2、代码实现

package com.chunsoft.sort; public class MergeSort { public static void main(String[] args) { int data[] = {9,8,7,6,5,8,4,3,2,1,11,0,90}; int length = data.length; F_MergeSort(data, 0, length-1); for(int num :data) { System.out.println(num); } } private static void F_MergeSort(int[] data,int low,int high) { int mid = (low + high)/2; if(low < high) { //左边切分 F_MergeSort(data,low,mid); //右边切分 F_MergeSort(data,mid+1,high); //归并 Sort(data,low,mid,high); } } private static void Sort(int[] data,int low,int mid,int high) { int[] temp = new int[high - low + 1]; int i = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; while(i <= mid && j <= high) { if(data[i] <= data[j]) { temp[k++] = data[i++]; }else{ temp[k++] = data[j++]; } } //将左边剩余元素全部移入新数组 while(i <= mid) { temp[k++] = data[i++]; } //将右边剩余元素全部移入新数组 while(j <= high) { temp[k++] = data[j++]; } //把新数组中的数覆盖data数组 int length = temp.length; for (int k2 = 0; k2 < length; k2++) data[low + k2] = temp[k2]; } }

3、复杂度和稳定性

（1）复杂度

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 空间复杂度为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n) 归并排序比较占用内存，但却是一种效率高且稳定的算法。

时间复杂度：O(nlogn) 空间复杂度：O(n)

（2）稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定的： 归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

（3）特点

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。