Robust/src/Benchmarks/oooJava/mergesort/BMergeSort4.java

   1 /**\r
   2  * 4-way split version of merge sort\r
   3  */\r
   4 \r
   5 public class MergeSort4 extends MergeSort {\r
   6 \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
  12     }\r
  13     if (args.length > 1) {\r
  14       parallelBranch = Integer.parseInt(args[1]);\r
  15     }\r
  16     MergeSort4 sort = new MergeSort4();\r
  17     sort.run(problemSize,parallelBranch);\r
  18   }\r
  19 \r
  20   public MergeSort4() {\r
  21     super();\r
  22   }\r
  23 \r
  24   public void runWorkAndTest() {\r
  25     sese run{\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
  30     }\r
  31 //    sese test{\r
  32 //      checkSorted(output);\r
  33 //    }\r
  34   }\r
  35 \r
  36   public int[] serializedSort(int A[], int low, int high) {\r
  37 \r
  38     int length = high - low;\r
  39 \r
  40     if (length <= QUICK_SIZE) {\r
  41       int[] R = new int[length];\r
  42       int max = R.length;\r
  43       int j = low;\r
  44       for (int i = 0; i < max; i++) {\r
  45           R[i] = A[j++];\r
  46       }\r
  47       quickSort(R, 0, R.length - 1);\r
  48       return R;\r
  49     } else {\r
  50 \r
  51       int q = length / 4;\r
  52       int idxs0 = q + low;\r
  53       int idxs1 = (2 * q) + low;\r
  54       int idxs2 = (3 * q) + low;\r
  55 \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
  60 \r
  61       int[] R = new int[high - low];\r
  62 \r
  63       merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
  64       return R;\r
  65     }\r
  66   }\r
  67 \r
  68   public int[] sort(int A[], int low, int high) {\r
  69     \r
  70     int length=high-low;\r
  71     \r
  72     if (length <= SERIALIZED_CUT_OFF) {\r
  73       return serializedSort(A, low, high);\r
  74     } else {\r
  75       if (length <= QUICK_SIZE) {\r
  76         int[] R = new int[length];\r
  77         int max = R.length;\r
  78         int j = low;\r
  79         for (int i = 0; i < max; i++) {\r
  80             R[i] = A[j++];\r
  81         }\r
  82         quickSort(R, 0, R.length-1);\r
  83         return R;\r
  84       } else {\r
  85         \r
  86         int q=length/4;\r
  87         int idxs0 = q+low;\r
  88         int idxs1 = (2 * q)+low;\r
  89         int idxs2 = (3 * q)+low;\r
  90 \r
  91         sese p1{\r
  92           int[] A_quarters0 = sort(A, low, idxs0);\r
  93         }\r
  94         sese p2{\r
  95           int[] A_quarters1 = sort(A, idxs0, idxs1);\r
  96         }\r
  97         sese p3{\r
  98           int[] A_quarters2 = sort(A, idxs1, idxs2);\r
  99         }\r
 100         // don't spawn off sese for last one...\r
 101         int[] A_quarters3 = sort(A, idxs2, idxs2+q);\r
 102 \r
 103         int[] R = new int[high - low];\r
 104 \r
 105         merge(A_quarters0, A_quarters1, A_quarters2, A_quarters3, R);\r
 106         return R;\r
 107       }\r
 108     }\r
 109   }\r
 110 \r
 111   public static void merge(int[] a1, int[] a2, int[] a3, int[] a4, int[] a) {\r
 112     int i1 = 0;\r
 113     int i2 = 0;\r
 114     int i3 = 0;\r
 115     int i4 = 0;\r
 116     int alength = a.length;\r
 117     int v1 = a1[0];\r
 118     int v2 = a2[0];\r
 119     int v3 = a3[0];\r
 120     int v4 = a4[0];\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
 126       if (v1 < v2) {\r
 127         if (v1 < v3) {\r
 128           if (v1 < v4) {\r
 129             a[i] = v1;\r
 130             // v1 smallest\r
 131             if (i1 < v1m) {\r
 132               v1 = a1[i1++];\r
 133             } else {\r
 134               v1 = 2147483647;\r
 135             }\r
 136           } else {\r
 137             a[i] = v4;\r
 138             // v4 smalles\r
 139             if (i4 < v4m) {\r
 140               v4 = a4[i4++];\r
 141             } else {\r
 142               v4 = 2147483647;\r
 143             }\r
 144           }\r
 145         } else {\r
 146           if (v3 < v4) {\r
 147             a[i] = v3;\r
 148             // v3 smallest\r
 149             if (i3 < v3m) {\r
 150               v3 = a3[i3++];\r
 151             } else {\r
 152               v3 = 2147483647;\r
 153             }\r
 154           } else {\r
 155             a[i] = v4;\r
 156             // v4 smallest\r
 157             if (i4 < v4m) {\r
 158               v4 = a4[i4++];\r
 159             } else {\r
 160               v4 = 2147483647;\r
 161             }\r
 162           }\r
 163         }\r
 164       } else {\r
 165         if (v2 < v3) {\r
 166           if (v2 < v4) {\r
 167             a[i] = v2;\r
 168             // v2 smallest\r
 169             if (i2 < v2m) {\r
 170               v2 = a2[i2++];\r
 171             } else {\r
 172               v2 = 2147483647;\r
 173             }\r
 174           } else {\r
 175             a[i] = v4;\r
 176             // v4 smallest\r
 177             if (i4 < v4m) {\r
 178               v4 = a4[i4++];\r
 179             } else {\r
 180               v4 = 2147483647;\r
 181             }\r
 182           }\r
 183         } else {\r
 184           if (v3 < v4) {\r
 185             a[i] = v3;\r
 186             // v3 smallest\r
 187             if (i3 < v3m) {\r
 188               v3 = a3[i3++];\r
 189             } else {\r
 190               v3 = 2147483647;\r
 191             }\r
 192           } else {\r
 193             a[i] = v4;\r
 194             // v4 smallest\r
 195             if (i4 < v4m) {\r
 196               v4 = a4[i4++];\r
 197             } else {\r
 198               v4 = 2147483647;\r
 199             }\r
 200           }\r
 201         }\r
 202       }\r
 203     }\r
 204   }\r
 205 \r
 206 }\r