1、自顶向下的归并排序
思想：
该方法运用了分治的思想，主要使用的方法是原地归并，它将一个数组分成两部分，左边数组从0开始，右边数组从mid+1开始，并将左边数组当前所指向的值与右边数组所指向的值比较，取两者中较小者，子数组若被取值，则该数组指针后移1位。
图示：
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61public class Merge {
private static Comparable[] aux;
public static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo)
return;
int mid = lo+(hi-lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
public static void merge(Comparable[] a,int lo,int mid,int hi){
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++)
aux[k]=a[k];
for(int k=lo;k<=hi;k++){
if(i>mid)
a[k]=aux[j++];
else if(j>hi)
a[k]=aux[i++];
else if(less(aux[j],aux[i]))
a[k]=aux[j++];
else
a[k]=aux[i++];
}
}
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a,int i,int j){
Comparable t = a[i];
a[i]=a[j];
a[j]=t;
}
private static void show(Comparable[] a){
for(int i=0;i<a.length;i++){
StdOut.print(a[i]+" ");
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a){
for(int i=1;i<a.length;i++){
if(less(a[i],a[i-1]))
return false;
}
return true;
}
public static void main(String[] args) {
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
说明：merge函数就是用来负责原地归并，创建了一个和待排序数组相同大小的aux数组，通过i和j表示左右两部分，通过分支能够看到分别代表左边走完取右半边，右半边走完用左半边，左边大于右边取右半边，右边大于左边取左半边。
时间复杂度：平均情况O(nlogn)，最坏O(nlogn)，最好O(nlogn)
空间复杂度：O(n)
稳定性：稳定
2、自底向上的归并排序
思想：
首先是进行两两归并，然后四四归并，如此这般进行下去。
图示：
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55public class MergeBU {
private static Comparable[] aux;
public static void sort(Comparable[] a){
int N = a.length;
aux = new Comparable[N];
for(int sz=1;sz<N;sz=sz+sz)
for(int lo=0;lo<N-sz;lo+=sz+sz)
merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
}
public static void merge(Comparable[] a,int lo,int mid,int hi){
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++)
aux[k]=a[k];
for(int k=lo;k<=hi;k++){
if(i>mid)
a[k]=aux[j++];
else if(j>hi)
a[k]=aux[i++];
else if(less(aux[j],aux[i]))
a[k]=aux[j++];
else
a[k]=aux[i++];
}
}
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a,int i,int j){
Comparable t = a[i];
a[i]=a[j];
a[j]=t;
}
private static void show(Comparable[] a){
for(int i=0;i<a.length;i++){
StdOut.print(a[i]+" ");
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a){
for(int i=1;i<a.length;i++){
if(less(a[i],a[i-1]))
return false;
}
return true;
}
public static void main(String[] args) {
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
时间复杂度：平均情况O(nlogn)，最坏O(nlogn)，最好O(nlogn)
空间复杂度：O(n)
稳定性：稳定
这其中的StdOut以及StdIn库使用自algs4这个jar包，下载地址：
https://algs4.cs.princeton.edu/code/algs4.jar