public class MergeSort4 extends MergeSort {\r
\r
public static void main(String[] args) {\r
- int problemSize= 1048576;\r
- if(args.length>0){\r
- problemSize=Integer.parseInt(args[0]);\r
+ int problemSize = 4194304;\r
+ if (args.length > 0) {\r
+ problemSize = Integer.parseInt(args[0]);\r
}\r
MergeSort4 sort = new MergeSort4();\r
sort.run(problemSize);\r
}\r
- \r
- public MergeSort4(){\r
+\r
+ public MergeSort4() {\r
super();\r
}\r
- \r
+\r
public void runWorkAndTest() {\r
sese run{\r
int output[]=sort(input, 0, input.length);\r
}\r
}\r
\r
-\r
public int[] serializedSort(int A[], int low, int high) {\r
- if(A.length<=SERIALIZED_CUT_OFF){\r
- return serializedSort(A, low, high);\r
- }else{\r
- if (A.length <= QUICK_SIZE) {\r
- int[] R=new int[high-low];\r
- int max=R.length;\r
- int j=low;\r
- for(int i=0;i<max;i++) {\r
- R[i]=A[j++];\r
- }\r
- quickSort(R, 0, R.length);\r
- return R;\r
- } else {\r
- int q = A.length / 4;\r
- \r
- int idxs0 = q;\r
- int idxs1 = 2 * q;\r
- int idxs2 = 3 * q;\r
- \r
- int[] A_quarters0 = serializedSort(A, 0, idxs0);\r
- int[] A_quarters1 = serializedSort(A, idxs0, idxs1);\r
- int[] A_quarters2 = serializedSort(A, idxs1, idxs2);\r
- int[] A_quarters3 = serializedSort(A, idxs2, A.length);\r
-\r
- int[] R=new int[high-low];\r
-\r
- merge(A_quarters0, A_quarters1, A_quarters2, A_quartes3, R);\r
- return R;\r
+\r
+ int length = high - low;\r
+\r
+ if (length <= QUICK_SIZE) {\r
+ int[] R = new int[length];\r
+ int max = R.length;\r
+ int j = low;\r
+ for (int i = 0; i < max; i++) {\r
+ R[i] = A[j++];\r
}\r
+ quickSort(R, 0, R.length - 1);\r
+ return R;\r
+ } else {\r
+\r
+ int q = length / 4;\r
+ int idxs0 = q + low;\r
+ int idxs1 = (2 * q) + low;\r
+ int idxs2 = (3 * q) + low;\r
+\r
+ int[] A_quarters0 = serializedSort(A, low, idxs0);\r
+ int[] A_quarters1 = serializedSort(A, idxs0, idxs1);\r
+ int[] A_quarters2 = serializedSort(A, idxs1, idxs2);\r
+ int[] A_quarters3 = serializedSort(A, idxs2, idxs2 + q);\r
+\r
+ int[] R = new int[high - low];\r
+\r
+ merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
+ return R;\r
}\r
}\r
\r
public int[] sort(int A[], int low, int high) {\r
- if(A.length<=SERIALIZED_CUT_OFF){\r
+ \r
+ int length=high-low;\r
+ \r
+ if (length <= SERIALIZED_CUT_OFF) {\r
return serializedSort(A, low, high);\r
- }else{\r
- if (A.length <= QUICK_SIZE) {\r
- int[] R=new int[high-low];\r
- int max=R.length;\r
- int j=low;\r
- for(int i=0;i<max;i++) {\r
- R[i]=A[j++];\r
- }\r
- quickSort(R, 0, R.length);\r
- return R;\r
+ } else {\r
+ if (length <= QUICK_SIZE) {\r
+ int[] R = new int[length];\r
+ int max = R.length;\r
+ int j = low;\r
+ for (int i = 0; i < max; i++) {\r
+ R[i] = A[j++];\r
+ }\r
+ quickSort(R, 0, R.length-1);\r
+ return R;\r
} else {\r
- int q = A.length / 4;\r
- \r
- int idxs0 = q;\r
- int idxs1 = 2 * q;\r
- int idxs2 = 3 * q;\r
- \r
+ \r
+ int q=length/4;\r
+ int idxs0 = q+low;\r
+ int idxs1 = (2 * q)+low;\r
+ int idxs2 = (3 * q)+low;\r
+\r
sese p1{\r
- int[] A_quarters0 = sort(A, 0, idxs0);\r
+ int[] A_quarters0 = sort(A, low, idxs0);\r
}\r
sese p2{\r
- int[] A_quarters1 = sort(A, idxs0, idxs1);\r
+ int[] A_quarters1 = sort(A, idxs0, idxs1);\r
}\r
sese p3{\r
- int[] A_quarters2 = sort(A, idxs1, idxs2);\r
+ int[] A_quarters2 = sort(A, idxs1, idxs2);\r
}\r
- //don't spawn off sese for last one...\r
- int[] A_quarters3 = sort(A, idxs2, A.length);\r
+ // don't spawn off sese for last one...\r
+ int[] A_quarters3 = sort(A, idxs2, idxs2+q);\r
\r
- int[] R=new int[high-low];\r
+ int[] R = new int[high - low];\r
\r
- merge(A_quarters0, A_quarters1, A_quarters2, A_quartes3, R);\r
- return R;\r
+ merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
+ return R;\r
}\r
}\r
}\r
\r
- public static void merge(int []a1, int []a2, int []a3, int[] a4, int[] a) {\r
- int i1=0;\r
- int i2=0;\r
- int i3=0;\r
- int i4=0;\r
- int alength=a.length;\r
- int v1=a1[0];\r
- int v2=a2[0];\r
- int v3=a3[0];\r
- int v4=a4[0];\r
- int v1m=a1.length;\r
- int v2m=a2.length;\r
- int v3m=a3.length;\r
- int v4m=a4.length;\r
- for(int i=0;i<alength;i++) {\r
- if (v1<v2) {\r
- if (v1<v3) {\r
- if (v1<v4) {\r
- a[i]=v1;\r
- //v1 smallest\r
- if (i1<v1m) {\r
- v1=a1[i1++];\r
- } else {\r
- v1=2147483647;\r
- }\r
- } else {\r
- //v4 smalles\r
- if (i4<v4m) {\r
- v4=a4[i4++];\r
- } else {\r
- v4=2147483647;\r
- }\r
- }\r
- } else {\r
- if (v3<v4) {\r
- //v3 smallest\r
- if (i3<v3m) {\r
- v3=a3[i3++];\r
- } else {\r
- v3=2147483647;\r
- }\r
- } else {\r
- //v4 smallest\r
- if (i4<v4m) {\r
- v4=a4[i4++];\r
- } else {\r
- v4=2147483647;\r
- }\r
- }\r
- }\r
+ public static void merge(int[] a1, int[] a2, int[] a3, int[] a4, int[] a) {\r
+ int i1 = 0;\r
+ int i2 = 0;\r
+ int i3 = 0;\r
+ int i4 = 0;\r
+ int alength = a.length;\r
+ int v1 = a1[0];\r
+ int v2 = a2[0];\r
+ int v3 = a3[0];\r
+ int v4 = a4[0];\r
+ int v1m = a1.length;\r
+ int v2m = a2.length;\r
+ int v3m = a3.length;\r
+ int v4m = a4.length;\r
+ for (int i = 0; i < alength; i++) {\r
+ if (v1 < v2) {\r
+ if (v1 < v3) {\r
+ if (v1 < v4) {\r
+ a[i] = v1;\r
+ // v1 smallest\r
+ if (i1 < v1m) {\r
+ v1 = a1[i1++];\r
+ } else {\r
+ v1 = 2147483647;\r
+ }\r
+ } else {\r
+ a[i] = v4;\r
+ // v4 smalles\r
+ if (i4 < v4m) {\r
+ v4 = a4[i4++];\r
+ } else {\r
+ v4 = 2147483647;\r
+ }\r
+ }\r
+ } else {\r
+ if (v3 < v4) {\r
+ a[i] = v3;\r
+ // v3 smallest\r
+ if (i3 < v3m) {\r
+ v3 = a3[i3++];\r
+ } else {\r
+ v3 = 2147483647;\r
+ }\r
+ } else {\r
+ a[i] = v4;\r
+ // v4 smallest\r
+ if (i4 < v4m) {\r
+ v4 = a4[i4++];\r
+ } else {\r
+ v4 = 2147483647;\r
+ }\r
+ }\r
+ }\r
} else {\r
- if (v2<v3) {\r
- if (v2<v4) {\r
- //v2 smallest\r
- if (i2<v2m) {\r
- v2=a2[i2++];\r
- } else {\r
- v2=2147483647;\r
- }\r
- } else {\r
- //v4 smallest\r
- if (i4<v4m) {\r
- v4=a4[i4++];\r
- } else {\r
- v4=2147483647;\r
- }\r
- }\r
- } else {\r
- if (v3<v4) {\r
- //v3 smallest\r
- if (i3<v3m) {\r
- v3=a3[i3++];\r
- } else {\r
- v3=2147483647;\r
- }\r
- } else {\r
- //v4 smallest\r
- if (i4<v4m) {\r
- v4=a4[i4++];\r
- } else {\r
- v4=2147483647;\r
- }\r
- }\r
- }\r
+ if (v2 < v3) {\r
+ if (v2 < v4) {\r
+ a[i] = v2;\r
+ // v2 smallest\r
+ if (i2 < v2m) {\r
+ v2 = a2[i2++];\r
+ } else {\r
+ v2 = 2147483647;\r
+ }\r
+ } else {\r
+ a[i] = v4;\r
+ // v4 smallest\r
+ if (i4 < v4m) {\r
+ v4 = a4[i4++];\r
+ } else {\r
+ v4 = 2147483647;\r
+ }\r
+ }\r
+ } else {\r
+ if (v3 < v4) {\r
+ a[i] = v3;\r
+ // v3 smallest\r
+ if (i3 < v3m) {\r
+ v3 = a3[i3++];\r
+ } else {\r
+ v3 = 2147483647;\r
+ }\r
+ } else {\r
+ a[i] = v4;\r
+ // v4 smallest\r
+ if (i4 < v4m) {\r
+ v4 = a4[i4++];\r
+ } else {\r
+ v4 = 2147483647;\r
+ }\r
+ }\r
+ }\r
}\r
}\r
}\r
+\r
}\r
/* Threshold values */\r
\r
// Cutoff for when to do sequential versus parallel merges\r
- public static int MERGE_SIZE;\r
+ public static int MERGE_SIZE;\r
\r
// Cutoff for when to do sequential quicksort versus parallel mergesort\r
- public static int QUICK_SIZE;\r
+ public static int QUICK_SIZE;\r
\r
// Cutoff for when to use insertion-sort instead of quicksort\r
- public static int INSERTION_SIZE;\r
- \r
- public static int SERIALIZED_CUT_OFF;\r
+ public static int INSERTION_SIZE;\r
\r
+ public static int SERIALIZED_CUT_OFF;\r
\r
protected int[] input;\r
protected int[] result;\r
protected int size;\r
\r
public void run(int size) {\r
- this.size=size;\r
- long startT=System.currentTimeMillis();\r
+ this.size = size;\r
+ long startT = System.currentTimeMillis();\r
initialize();\r
- System.out.println("init time="+(System.currentTimeMillis()-startT));\r
+ System.out.println("init time=" + (System.currentTimeMillis() - startT));\r
runWorkAndTest();\r
}\r
\r
}\r
\r
public void initialize() {\r
- \r
- SERIALIZED_CUT_OFF=size/16;\r
- \r
+\r
+ SERIALIZED_CUT_OFF = size / 32;\r
+\r
input = new int[size];\r
result = new int[size];\r
\r
sese run{\r
sort(input);\r
}\r
- sese test{\r
- checkSorted(input);\r
- }\r
+// sese test{\r
+// checkSorted(input);\r
+// }\r
}\r
- \r
- public void sort(int A[]){\r
+\r
+ public void sort(int A[]) {\r
}\r
\r
protected void checkSorted(int[] array) {\r
\r
protected void merge(int A[], int B[], int out[]) {\r
\r
- if (A.length <= MERGE_SIZE) {\r
+ if (A.length <= SERIALIZED_CUT_OFF) {\r
sequentialMerge(A, B, out);\r
} else {\r
- int aHalf = A.length >>> 1; /* l33t shifting h4x!!! */\r
- int bSplit = findSplit(A[aHalf], B);\r
+ if (A.length <= MERGE_SIZE) {\r
+ sequentialMerge(A, B, out);\r
+ } else {\r
+ int aHalf = A.length >>> 1; /* l33t shifting h4x!!! */\r
+ int bSplit = findSplit(A[aHalf], B);\r
+\r
+ int[] A_split0 = new int[aHalf];\r
+ int[] A_split1 = new int[A.length - aHalf];\r
+ for (int i = 0; i < aHalf; i++) {\r
+ A_split0[i] = A[i];\r
+ }\r
+ for (int i = aHalf; i < A.length; i++) {\r
+ A_split1[i - aHalf] = A[i];\r
+ }\r
\r
- int[] A_split0 = new int[aHalf];\r
- int[] A_split1 = new int[A.length - aHalf];\r
- for (int i = 0; i < aHalf; i++) {\r
- A_split0[i] = A[i];\r
- }\r
- for (int i = aHalf; i < A.length; i++) {\r
- A_split1[i - aHalf] = A[i];\r
- }\r
+ int[] B_split0 = new int[bSplit];\r
+ int[] B_split1 = new int[B.length - bSplit];\r
+ for (int i = 0; i < bSplit; i++) {\r
+ B_split0[i] = B[i];\r
+ }\r
+ for (int i = bSplit; i < B.length; i++) {\r
+ B_split1[i - bSplit] = B[i];\r
+ }\r
\r
- int[] B_split0 = new int[bSplit];\r
- int[] B_split1 = new int[B.length - bSplit];\r
- for (int i = 0; i < bSplit; i++) {\r
- B_split0[i] = B[i];\r
- }\r
- for (int i = bSplit; i < B.length; i++) {\r
- B_split1[i - bSplit] = B[i];\r
- }\r
+ int outSplit = aHalf + bSplit;\r
+ int[] out_split0 = new int[outSplit];\r
+ int[] out_split1 = new int[out.length - outSplit];\r
\r
- int outSplit = aHalf + bSplit;\r
- int[] out_split0 = new int[outSplit];\r
- int[] out_split1 = new int[out.length - outSplit];\r
+ merge(A_split0, B_split0, out_split0);\r
+ merge(A_split1, B_split1, out_split1);\r
+\r
+ for (int i = 0; i < outSplit; i++) {\r
+ out[i] = out_split0[i];\r
+ }\r
+ for (int i = outSplit; i < out.length; i++) {\r
+ out[i] = out_split1[i - outSplit];\r
+ }\r
\r
- merge(A_split0, B_split0, out_split0);\r
- merge(A_split1, B_split1, out_split1);\r
- \r
- for (int i = 0; i < outSplit; i++) {\r
- out[i]=out_split0[i]; \r
- }\r
- for (int i = outSplit; i < out.length; i++) {\r
- out[i]=out_split1[i - outSplit];\r
}\r
- \r
}\r
- \r
+\r
}\r
\r
/** A standard sequential merge **/\r
\r
/** A standard sequential quicksort **/\r
protected void quickSort(int array[], int lo, int hi) {\r
-// int lo = 0;\r
-// int hi = array.length - 1;\r
+ // int lo = 0;\r
+ // int hi = array.length - 1;\r
// If under threshold, use insertion sort\r
int[] arr = array;\r
if (hi - lo + 1l <= INSERTION_SIZE) {\r
\r
int partition = arr[mid];\r
\r
- while(true){\r
+ while (true) {\r
\r
while (arr[right] > partition)\r
--right;\r
\r
}\r
\r
- quickSort(arr,lo,left+1);\r
- quickSort(arr,left+1,hi);\r
+ quickSort(arr, lo, left + 1);\r
+ quickSort(arr, left + 1, hi);\r
\r
}\r
\r
projects / IRC.git / commitdiff