| 100 | } |
| 101 | |
| 102 | private static <T> void heapSort(List<T> list, Comparator<? super T> comparator, |
| 103 | int begin, int end) |
| 104 | { |
| 105 | int count = end - begin; |
| 106 | for (int i = count / 2 - 1; i >= 0; --i) { |
| 107 | siftDown(list, comparator, i, count, begin); |
| 108 | } |
| 109 | for (int i = count - 1; i > 0; --i) { |
| 110 | // swap begin and begin + i |
| 111 | T swap = list.get(begin + i); |
| 112 | list.set(begin + i, list.get(begin)); |
| 113 | list.set(begin, swap); |
| 114 | |
| 115 | siftDown(list, comparator, 0, i, begin); |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | private static <T> void siftDown(List<T> list, Comparator<? super T> comparator, |
| 120 | int i, int count, int offset) |