分析：
將一個數(shù)組拆成兩個數(shù)組分別進(jìn)行排序膜蛔，然后將兩個排序好的數(shù)組進(jìn)行合并韵洋。
JAVA代碼實(shí)現(xiàn)：
public class Main {
public static void main(String[] args) {
int[] arr = new int[100];
for(int i=0;i<100;i++) {
arr[i] = (int) (Math.random() * 100);
}
sort(arr);
for(int i=0;i<100;i++){
System.out.println(arr[i]);
}
}
public static void sort(int[] arr) {
sort(arr, 0, arr.length-1);
}
//對數(shù)組中的[start, end]進(jìn)行排序
private static void sort(int[] arr, int begin, int end) {
if(begin >= end) { //邊界
return;
}
int half = (begin + end) /2;
//先排序左邊
sort(arr, begin, half);
//再排序右邊
sort(arr, half+1, end);
merge(arr, begin, half, end);
}
private static void merge(int[] arr, int begin, int half ,int end) {
int[] cache = new int[end - begin + 1];
int k = 0;
int l = begin;
int r = half+1;
while(l <= half && r <= end) {
if(arr[l] <= arr[r]) {
cache[k++] = arr[l++];
}
else{
cache[k++] = arr[r++];
}
}
while(l<=half){
cache[k++] = arr[l++];
}
while(r<=end){
cache[k++] = arr[r++];
}
for(int i=begin;i<=end;i++){
arr[i] = cache[i-begin];
}
}
}
