| 52 | } |
| 53 | |
| 54 | private static <T > void introSort(List<T> list, |
| 55 | Comparator<? super T> comparator, int begin, int end, int limit) |
| 56 | { |
| 57 | while (end - begin > SORT_SIZE_THRESHOLD) { |
| 58 | if (limit == 0) { |
| 59 | heapSort(list, comparator, begin, end); |
| 60 | return; |
| 61 | } |
| 62 | limit >>= 1; |
| 63 | |
| 64 | // median of three |
| 65 | T a = list.get(begin); |
| 66 | T b = list.get(begin + (end - begin) / 2 + 1); |
| 67 | T c = list.get(end - 1); |
| 68 | T median; |
| 69 | if (comparator.compare(a, b) < 0) { |
| 70 | median = comparator.compare(b, c) < 0 ? |
| 71 | b : (comparator.compare(a, c) < 0 ? c : a); |
| 72 | } else { |
| 73 | median = comparator.compare(b, c) > 0 ? |
| 74 | b : (comparator.compare(a, c) > 0 ? c : a); |
| 75 | } |
| 76 | |
| 77 | // partition |
| 78 | int pivot, i = begin, j = end; |
| 79 | for (;;) { |
| 80 | while (comparator.compare(list.get(i), median) < 0) { |
| 81 | ++i; |
| 82 | } |
| 83 | --j; |
| 84 | while (comparator.compare(median, list.get(j)) < 0) { |
| 85 | --j; |
| 86 | } |
| 87 | if (i >= j) { |
| 88 | pivot = i; |
| 89 | break; |
| 90 | } |
| 91 | T swap = list.get(i); |
| 92 | list.set(i, list.get(j)); |
| 93 | list.set(j, swap); |
| 94 | ++i; |
| 95 | } |
| 96 | |
| 97 | introSort(list, comparator, pivot, end, limit); |
| 98 | end = pivot; |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | private static <T> void heapSort(List<T> list, Comparator<? super T> comparator, |
| 103 | int begin, int end) |