一、
思路：
归并排序是分治法和递归的典型应用。归并排序分为两种实现方法：自顶向下和自底向上。自顶向下先归后并，即先将待排序数组递归分割，然后将分割后的数组进行合并排序；而自底向上没有使用递归，而是直接使用迭代“手动”进行分割，然后进行合并排序。自底向上由于没有使用递归，减少了栈空间的使用。
代码：
top to bottom:
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
35public static void mergeSort(int[] arr) {
int low = 0;
int high = arr.length - 1;
split(arr, low, high);
}
public static void split(int[] arr,int low,int high) {
if (low < high) {
int mid = (low + high)/2;
split(arr, low, mid);
split(arr, mid+1, high);
merge(arr, low, mid, high);
}
}
public static void merge(int [] arr,int low,int mid,int high) {
int[] temp = new int[high - low + 1];
int k = 0;
int i = low;
int j = mid + 1;
while(i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
}else {
temp[k++] = arr[j++];
}
}
while(i <= mid) {
temp[k++] = arr[i++];
}
while(j <= high) {
temp[k++] = arr[j++];
}
for(int l = low;l <= high;l++) {
arr[l] = temp[l-low];
}
}
bottom to top：
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
public void mergeSort1(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int k = 1;
while(k < arr.length) {
mergePass(arr, k);
k = k*2;
}
}
public void mergePass(int[] arr,int k) {
int start = 0;
while(start + 2*k - 1 < arr.length) {
int mid = start + k -1;
int high = start + 2*k - 1;
merge(arr, start, mid, high);
start = start + 2*k;
}
if (start + k - 1 < arr.length) {
merge(arr, start, start + k - 1, arr.length - 1);
}
}
public static void merge(int[] arr,int low,int mid,int high) {
int[] temp = new int[high-low+1];
int i = low;
int j = mid+1;
int m = 0;
while(i <= mid && j<=high) {
if (arr[i] <= arr[j]) {
temp[m++] = arr[i++];
}else {
temp[m++] = arr[j++];
}
}
while(i <= mid) {
temp[m++] = arr[i++];
}
while(j <= high) {
temp[m++] = arr[j++];
}
for(int k = 0;k < temp.length;k++) {
arr[k+low] = temp[k];
}
}
复杂度分析及总结：
时间复杂度：
O(nlogn)。由于递归深度为logn，每层递归需要进行n次比较，所以时间复杂度为O(nlogn)。
空间复杂度：
O(n)。由于递归深度为logn，且在合并时会创建大小为n的临时数组，所以空间复杂度为O(n)+O(logn)，即O(n)。