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