package com.acwer.queue;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
public class 归并排序 {
public static void main(String[] args) {
int[] arr=new int[10000000];
for (int i = 0; i < arr.length; i++) {
arr[i]=(new Random().nextInt(100));
}
long ts=(new Date()).getTime();
mergeSort(arr,0,arr.length-1,new int[arr.length]);
System.out.println(((new Date()).getTime()-ts)*1.0/1000);
}
public static void mergeSort(int[] arr,int left,int right,int[]temp){
if(left
int mid=(left+right)/2;
mergeSort(arr,left,mid,temp);
mergeSort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr,int left,int mid,int right,int[]temp){
int i=left;
int j=mid+1;
int t=0;
while (i<=mid&&j<=right){
if(arr[i]<=arr[j]){
temp[t++]=arr[i++];
}else{
temp[t++]=arr[j++];
}
}
while (i<=mid){
temp[t++]=arr[i++];
}
while (j<=right){
temp[t++]=arr[j++];
}
t = 0;
i= left;
while( i <= right){
arr[i++]=temp[t++];
}
}
}