import lib.Sort;
import lib.IntArrayConsumer;

/**
Quicksort with tail recursion optimization.
<p>
Reduces call stack extra non-input memory worst case from N to log(N).
<p>
For that to be possible, it always does the tail optimization on the longest side.
*/
public class QuickSortTail implements IntArrayConsumer {

    public void accept(final int[] in) {
        acceptRecursive(in, 0, in.length - 1);
    }

    private static void acceptRecursive(
            final int[] in,
            int leftI,
            int rightI) {
        while (leftI < rightI) {

            // Same as the non-optimized version.
            int smallI = leftI;
            int bigI = leftI;
            final int pivot = in[rightI];
            while (bigI < rightI) {
                final int big = in[bigI];
                if (big < pivot) {
                    int smallBuf = in[smallI];
                    in[smallI] = big;
                    in[bigI] = smallBuf;
                    smallI++;
                }
                bigI++;
            }
            in[rightI] = in[smallI];
            in[smallI] = pivot;

            // Tail optimize on the longer side.
            if (smallI - leftI > rightI - smallI) {
                acceptRecursive(in, smallI + 1, rightI);
                rightI = smallI - 1;
            } else {
                acceptRecursive(in, leftI, smallI - 1);
                leftI = smallI + 1;
            }
        }
    }

    public static void main(String[] args) throws Throwable {
        Sort.test(args[0], new QuickSortTail());
    }
}