Performs sorting based on the double values natural comparator. Double#NaN values will not be handled appropriately. @param x the array to sort @param start the starting index (inclusive) to sort @param end the ending index (exclusive) to sort
(double[] x, int start, int end)
| 142 | * @param end the ending index (exclusive) to sort |
| 143 | */ |
| 144 | public static void sort(double[] x, int start, int end) |
| 145 | { |
| 146 | int a = start; |
| 147 | int n = end-start; |
| 148 | if (n < 7)/* Insertion sort on smallest arrays */ |
| 149 | { |
| 150 | insertionSort(x, a, end); |
| 151 | return; |
| 152 | } |
| 153 | |
| 154 | int pm = a + (n/2); /* Small arrays, middle element */ |
| 155 | if (n > 7) |
| 156 | { |
| 157 | int pl = a; |
| 158 | int pn = a + n - 1; |
| 159 | if (n > 40) /* Big arrays, pseudomedian of 9 */ |
| 160 | { |
| 161 | int s = n / 8; |
| 162 | pl = med3(x, pl, pl + s, pl + 2 * s); |
| 163 | pm = med3(x, pm - s, pm, pm + s); |
| 164 | pn = med3(x, pn - 2 * s, pn - s, pn); |
| 165 | } |
| 166 | pm = med3(x, pl, pm, pn); /* Mid-size, med of 3 */ |
| 167 | } |
| 168 | double pivotValue = x[pm]; |
| 169 | |
| 170 | int pa = a, pb = pa, pc = end - 1, pd = pc; |
| 171 | while (true) |
| 172 | { |
| 173 | while (pb <= pc && x[pb] <= pivotValue) |
| 174 | { |
| 175 | if (x[pb] == pivotValue) |
| 176 | swap(x, pa++, pb); |
| 177 | pb++; |
| 178 | } |
| 179 | while (pc >= pb && x[pc] >= pivotValue) |
| 180 | { |
| 181 | if (x[pc] == pivotValue) |
| 182 | swap(x, pc, pd--); |
| 183 | pc--; |
| 184 | } |
| 185 | if (pb > pc) |
| 186 | break; |
| 187 | swap(x, pb++, pc--); |
| 188 | } |
| 189 | |
| 190 | |
| 191 | int s; |
| 192 | int pn = end; |
| 193 | s = Math.min(pa - a, pb - pa); |
| 194 | vecswap(x, a, pb - s, s); |
| 195 | s = Math.min(pd - pc, pn - pd - 1); |
| 196 | vecswap(x, pb, pn - s, s); |
| 197 | |
| 198 | //recurse |
| 199 | if ((s = pb - pa) > 1) |
| 200 | sort(x, a, a+s); |
| 201 | if ((s = pd - pc) > 1) |