原理
归并排序是通过将一个大数组不断划分为小数组，使小数组内部有序，然后再将有序的小数组合并为一个有序的大数组。
归并排序图解
递归实现
每次从中点将数组划分为两个小数组，两个小数组需内部有序，故划分为只有一个元素时终止递归。然后合并两个有序的小数组，具体就是通过利用一个辅助数组，遍历两个小数组，将较小元素复制到辅助数组之中，最后将辅助数组拷贝到原数组中，实现归并排序。
递归实现归并排序
import java.io.*;
public class Main {
public static int MAXN=100000;
// 原数组
public static int[] arr=new int[MAXN];
// 辅助数组
public static int[] help=new int[MAXN];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in=new StreamTokenizer(br);
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
//n个整数
int n=(int) in.nval;
for(int i=0;i<n;i++){
in.nextToken();
arr[i]=(int) in.nval;
}
mergeSort(0,n-1);
for(int i=0;i<n;i++){
out.print(arr[i]+" ");
}
out.flush();;
br.close();
out.close();
}
// 递归实现归并排序
public static void mergeSort(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
mergeSort(l,mid);
mergeSort(mid+1,r);
merge(l,mid,r);
}
// 合并两个有序数组
public static void merge(int l,int mid,int r){
int a=l;
int b=l,c=mid+1;
while(b<=mid && c<=r){
help[a++]=arr[b]<=arr[c]?arr[b++]:arr[c++];
}
while(b<=mid) help[a++]=arr[b++];
while(c<=r) help[a++]=arr[c++];
for(int i=l;i<=r;i++) arr[i]=help[i];
}
}
非递归实现
定义一个步长变量step，初始值=1，每次*2，每次左侧和右侧都取step数量的元素组成两个数组，然后对该数组进行merge。
非递归实现归并排序
非递归实现归并排序只有mergeSort()方法不同，其他部分与递归实现归并排序相同
// 归并排序非递归版
public static void mergeSort2(int l，int r) {
int n = r+1;
for (int m,step = 1; step < n; step <<= 1) {
while (l < n) {
// 左侧最后一个元素所在的位置
m = l + step - 1;
if (m + 1 >= n) {//若右侧没有元素了，可直接退出
break;
}
// 右侧最后一个元素所在位置
r = Math.min(l + (step << 1) - 1, n - 1);
merge(arr, l, m, r);
// 下一组数左侧元素起始位置
l = r + 1;
}
}
}
时间复杂度、空间复杂度分析
首先分析两个算法都用到的merge()函数
public static void merge(int l,int mid,int r){
int a=l;
int b=l,c=mid+1;
while(b<=mid && c<=r){
help[a++]=arr[b]<=arr[c]?arr[b++]:arr[c++];
}
while(b<=mid) help[a++]=arr[b++];
while(c<=r) help[a++]=arr[c++];
for(int i=l;i<=r;i++) arr[i]=help[i];
}
该方法一次遍历，将两个有序数组合并，因此时间复杂度为O（n）
其中借助到了辅助数组，故空间复杂度为O（n）。
递归算法
public static void mergeSort(int l,int r){
if(l==r) return;
int mid=(l+r)/2;
mergeSort(l,mid);
mergeSort(mid+1,r);
merge(l,mid,r);
}
借助master公式，T(N)=2*T(N/2)+O(N)
a=2,b=2,c=1，logab=c，因此时间复杂度为O（n * logn）
非递归算法
public static void mergeSort2(int l，int r) {
int n = r+1;
//O(logn)
for (int m,step = 1; step < n; step <<= 1) {
//内部分组merge，O(n)
while (l < n) {
m = l + step - 1;
if (m + 1 >= n) {
break;
}
r = Math.min(l + (step << 1) - 1, n - 1);
merge(arr, l, m, r);
l = r + 1;
}
}
}
因此，时间复杂度为O（n * logn）
