| 159 | } |
| 160 | |
| 161 | private static <T > void introSort(T[] array, |
| 162 | Comparator<? super T> comparator, int begin, int end, int limit) |
| 163 | { |
| 164 | while (end - begin > SORT_SIZE_THRESHOLD) { |
| 165 | if (limit == 0) { |
| 166 | heapSort(array, comparator, begin, end); |
| 167 | return; |
| 168 | } |
| 169 | limit >>= 1; |
| 170 | |
| 171 | // median of three |
| 172 | T a = array[begin]; |
| 173 | T b = array[begin + (end - begin) / 2 + 1]; |
| 174 | T c = array[end - 1]; |
| 175 | T median; |
| 176 | if (comparator.compare(a, b) < 0) { |
| 177 | median = comparator.compare(b, c) < 0 ? |
| 178 | b : (comparator.compare(a, c) < 0 ? c : a); |
| 179 | } else { |
| 180 | median = comparator.compare(b, c) > 0 ? |
| 181 | b : (comparator.compare(a, c) > 0 ? c : a); |
| 182 | } |
| 183 | |
| 184 | // partition |
| 185 | int pivot, i = begin, j = end; |
| 186 | for (;;) { |
| 187 | while (comparator.compare(array[i], median) < 0) { |
| 188 | ++i; |
| 189 | } |
| 190 | --j; |
| 191 | while (comparator.compare(median, array[j]) < 0) { |
| 192 | --j; |
| 193 | } |
| 194 | if (i >= j) { |
| 195 | pivot = i; |
| 196 | break; |
| 197 | } |
| 198 | T swap = array[i]; |
| 199 | array[i] = array[j]; |
| 200 | array[j] = swap; |
| 201 | ++i; |
| 202 | } |
| 203 | |
| 204 | introSort(array, comparator, pivot, end, limit); |
| 205 | end = pivot; |
| 206 | } |
| 207 | } |
| 208 | |
| 209 | private static <T> void heapSort(T[] array, Comparator<? super T> comparator, |
| 210 | int begin, int end) |