其实也就是二路归并排序。
# 1. 二路归并排序
写这个算法主要需要理解分治和递归的思想。
~~~
public void twoWayMergeSort(int[] arr) {
twoWaymergeSort(arr, 0, arr.length - 1);
}
private void twoWaymergeSort(int[] arr, int low, int high) {
if(low < high){
int mid = (low + high) / 2;
twoWaymergeSort(arr, low, mid);
twoWaymergeSort(arr, mid+1, high);
merge(arr, low, mid, high);
}
}
private void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high -low + 1];
int index = 0;
int p = low, q = mid + 1;
while(p <= mid && q <= high){
if(arr[p] > arr[q]){
temp[index++] = arr[q++];
}else{
temp[index++] = arr[p++];
}
}
while(p <= mid){
temp[index++] = arr[p++];
}
while(q <= high){
temp[index++] = arr[q++];
}
for (int i = 0; i < temp.length; i++) {
arr[low + i] = temp[i];
}
}
~~~
