package algorithm;
import java.security.SecureRandom;
import java.util.Random;
public class MergeSort {
public static void merge(int[] pData,int low,int mid,int high){
int[]b=new int[high-low+1];
int s=low;
int t=mid+1;
int k=0;
while(s<=mid&&t<=high){
if(pData[s]<=pData[t])
b[k++]=pData[s++];
else
b[k++]=pData[t++];
}
while(s<=mid)
b[k++]=pData[s++];
while(t<=high)
b[k++]=pData[t++];
for(int i=0;i<b.length;i++){
pData[low+i]=b[i];
}
}
public static void mergeSort(int[] pData,int low,int high){
if(low < high){
mergeSort(pData,low,(low+high)/2);
mergeSort(pData,(low+high)/2+1,high);
merge(pData,low,(low+high)/2,high);
}
}
public static void main(String[] args){
Random random = new SecureRandom();
int[] pData = new int[1000000];
for(int i=0;i<pData.length;i++){
pData[i] = random.nextInt(Integer.MAX_VALUE);
}
System.out.println(System.currentTimeMillis());
mergeSort(pData, 0, pData.length-1);
System.out.println(System.currentTimeMillis());
}
}