蛇足風味

再帰しないクイックソートはこんな感じです。不安定です。（正しさは証明してないので要注意。）

static <T extends Comparable<? super T>> void qsort(T[] array, int begin, int end)
{
    int[] stack = new int[64];
    int sp = 0;
    for (;;) {
        if (end <= begin + 10) {
            for (int i = begin + 1; i < end; i++) {
                T x = array[i];
                int j = i;
                while (--j >= begin && x.compareTo(array[j]) < 0)
                    array[j + 1] = array[j];
                array[j + 1] = x;
            }
            if (sp == 0) return;
            end = stack[--sp]; begin = stack[--sp];
        } else {
            T a = array[begin], b = array[(begin + end) / 2], c = array[end - 1];
            T pivot = (a.compareTo(b) < 0 ? 
                       (b.compareTo(c) < 0 ? b : a.compareTo(c) < 0 ? c : a) : 
                       (c.compareTo(b) < 0 ? b : c.compareTo(a) < 0 ? c : a));
            int l = begin - 1, r = end;
            for (;;) {
                while (pivot.compareTo(array[++l]) > 0) ;
                while (pivot.compareTo(array[--r]) < 0) ;
                if (l >= r) break;
                T t = array[l]; array[l] = array[r]; array[r] = t;
            }
            if (l - begin >= end - l) {
                stack[sp++] = begin; stack[sp++] = l; begin = l;
            } else {
                stack[sp++] = l; stack[sp++] = end; end = l;
            }
        }
    }
}