2 * 4-way split version of merge sort
\r
5 public class MergeSort4 extends MergeSort {
\r
7 public static void main(String[] args) {
\r
8 int problemSize = 4194304;
\r
9 int parallelBranch=32;
\r
10 if (args.length > 0) {
\r
11 problemSize = Integer.parseInt(args[0]);
\r
13 if (args.length > 1) {
\r
14 parallelBranch = Integer.parseInt(args[1]);
\r
16 MergeSort4 sort = new MergeSort4();
\r
17 sort.run(problemSize,parallelBranch);
\r
20 public MergeSort4() {
\r
24 public void runWorkAndTest() {
\r
26 long startT=System.currentTimeMillis();
\r
27 int output[]=sort(input, 0, input.length);
\r
28 long endT=System.currentTimeMillis();
\r
29 System.out.println("running time="+(endT-startT));
\r
32 // checkSorted(output);
\r
36 public int[] serializedSort(int A[], int low, int high) {
\r
38 int length = high - low;
\r
40 if (length <= QUICK_SIZE) {
\r
41 int[] R = new int[length];
\r
44 for (int i = 0; i < max; i++) {
\r
47 quickSort(R, 0, R.length - 1);
\r
52 int idxs0 = q + low;
\r
53 int idxs1 = (2 * q) + low;
\r
54 int idxs2 = (3 * q) + low;
\r
56 int[] A_quarters0 = serializedSort(A, low, idxs0);
\r
57 int[] A_quarters1 = serializedSort(A, idxs0, idxs1);
\r
58 int[] A_quarters2 = serializedSort(A, idxs1, idxs2);
\r
59 int[] A_quarters3 = serializedSort(A, idxs2, idxs2 + q);
\r
61 int[] R = new int[high - low];
\r
63 merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);
\r
68 public int[] sort(int A[], int low, int high) {
\r
70 int length=high-low;
\r
72 if (length <= SERIALIZED_CUT_OFF) {
\r
73 return serializedSort(A, low, high);
\r
75 if (length <= QUICK_SIZE) {
\r
76 int[] R = new int[length];
\r
79 for (int i = 0; i < max; i++) {
\r
82 quickSort(R, 0, R.length-1);
\r
88 int idxs1 = (2 * q)+low;
\r
89 int idxs2 = (3 * q)+low;
\r
92 int[] A_quarters0 = sort(A, low, idxs0);
\r
95 int[] A_quarters1 = sort(A, idxs0, idxs1);
\r
98 int[] A_quarters2 = sort(A, idxs1, idxs2);
\r
100 // don't spawn off sese for last one...
\r
101 int[] A_quarters3 = sort(A, idxs2, idxs2+q);
\r
103 int[] R = new int[high - low];
\r
105 merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);
\r
111 public static void merge(int[] a1, int[] a2, int[] a3, int[] a4, int[] a) {
\r
116 int alength = a.length;
\r
121 int v1m = a1.length;
\r
122 int v2m = a2.length;
\r
123 int v3m = a3.length;
\r
124 int v4m = a4.length;
\r
125 for (int i = 0; i < alength; i++) {
\r