| 207 | } |
| 208 | |
| 209 | private static <T> void heapSort(T[] array, Comparator<? super T> comparator, |
| 210 | int begin, int end) |
| 211 | { |
| 212 | int count = end - begin; |
| 213 | for (int i = count / 2 - 1; i >= 0; --i) { |
| 214 | siftDown(array, comparator, i, count, begin); |
| 215 | } |
| 216 | for (int i = count - 1; i > 0; --i) { |
| 217 | // swap begin and begin + i |
| 218 | T swap = array[begin + i]; |
| 219 | array[begin + i] = array[begin]; |
| 220 | array[begin] = swap; |
| 221 | |
| 222 | siftDown(array, comparator, 0, i, begin); |
| 223 | } |
| 224 | } |
| 225 | |
| 226 | private static <T> void siftDown(T[] array, Comparator<? super T> comparator, |
| 227 | int i, int count, int offset) |