korayucar
7/7/2016 - 6:36 AM
bottom up merge sort with exactly n auxilary space. Some testing code included. Interestingly on my machine sort time grows slower than line
bottom up merge sort with exactly n auxilary space. Some testing code included. Interestingly on my machine sort time grows slower than linear as opposed to n(lgn). Some refactoring might be good on variable names and stuff.
public class MergeSort{
public static void sort(int[] arr){
int granularity = 1;
int[] copy = new int[arr.length];
boolean sourceOriginal=true;
while(granularity <= arr.length){
// System.out.println(" Used Memory in granularity : " + granularity + " is "
// + (instance.totalMemory() - instance.freeMemory()) / mb);
for(int i = 0 ; i < arr.length ; i+= granularity*2){
merge( i ,
Math.min(i + granularity, arr.length) ,
Math.min(i + granularity, arr.length) ,
Math.min(i + 2 * granularity, arr.length) ,
i,
sourceOriginal ? arr : copy,
sourceOriginal ? copy : arr);
}
granularity <<= 1;
sourceOriginal = !sourceOriginal;
}
if(!sourceOriginal)
merge(0,arr.length, 0 , 0 ,0, copy , arr);
}
private static void merge(int startFirst , int endFirst , int startSecond , int endSecond , int targetIndex, int[] source , int[] target){
while(startFirst < endFirst || startSecond < endSecond){
if(startFirst < endFirst && (startSecond == endSecond || source[startFirst] < source[startSecond] ) ){
target[targetIndex] = source[startFirst];
startFirst++;
}
else{
target[targetIndex] = source[startSecond];
startSecond++;
}
targetIndex++;
}
}
static Runtime instance = Runtime.getRuntime();
static int mb = 1024 * 1024;
public static void main(String... args){
Random r = new Random();
for(int j = 1 ; j < 100000002 ; j*=10) {
System.out.println();
System.gc();
System.out.println("Used Memory after gc: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
int[] arr = new int[j];
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
System.out.println("Used Memory after array creation: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
long startTime = System.nanoTime();
MergeSort.sort(arr);
long endTime = System.nanoTime();
System.out.println("Used Memory after sort: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
System.out.println("time passed : " +(endTime - startTime)/1000+" μs");
for (int i = 1; i < arr.length; i++) {
if(arr[i] < arr[i-1] )
throw new IllegalStateException("sort failed");
}
}
}
}