void (int[] I, int[] V, int initStart, int initLen, int h) { Deque<Integer> startStack = new ArrayDeque<>(); Deque<Integer> lenStack = new ArrayDeque<>(); startStack.push(initStart); lenStack.push(initLen); while (!startStack.isEmpty()) { int start = startStack.pop(); int len = lenStack.pop(); if (len < 16) { selectSplit(I, V, start, len, h); continue; } int pivot = V[I[start + len / 2] + h]; int endLessThanIndex = 0; int endLessOrEqualIndex = 0; for (int i = start; i < start + len; i++) { if (V[I[i] + h] < pivot) { endLessThanIndex++; } if (V[I[i] + h] == pivot) { endLessOrEqualIndex++; } } endLessThanIndex += start; endLessOrEqualIndex += endLessThanIndex; int i = start; int currentEqualIndex = 0; int currentGreaterIndex = 0; while (i < endLessThanIndex) { if (V[I[i] + h] < pivot) { i++; } else if (V[I[i] + h] == pivot) { swap(I, i, endLessThanIndex + currentEqualIndex); currentEqualIndex++; } else { swap(I, i, endLessOrEqualIndex + currentGreaterIndex); currentGreaterIndex++; } } while (endLessThanIndex + currentEqualIndex < endLessOrEqualIndex) { if (V[I[endLessThanIndex + currentEqualIndex] + h] == pivot) { currentEqualIndex++; } else { swap(I, endLessThanIndex + currentEqualIndex, endLessOrEqualIndex + currentGreaterIndex); currentGreaterIndex++; } } for (i = endLessThanIndex; i < endLessOrEqualIndex; i++) { V[I[i]] = endLessOrEqualIndex - 1; } if (endLessThanIndex == endLessOrEqualIndex - 1) { I[endLessThanIndex] = -1; } if (endLessThanIndex > start) { startStack.push(start); lenStack.push(endLessThanIndex - start); } if (start + len > endLessOrEqualIndex) { startStack.push(endLessOrEqualIndex); lenStack.push(start + len - endLessOrEqualIndex); } } }