/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.arrays;

import net.ranides.assira.collection.IntComparator;

@SuppressWarnings({
    "PMD"
})
public final class IntArraySort {

    private static final int SMALL = 7;
    
    private static final int MEDIUM = 50;
    
    /**
     * The size of a digit used during radix sort (must be a power of 2).
     */
    private static final int DIGIT_BITS = 8;
    /**
     * The mask to extract a digit of {@link #DIGIT_BITS} bits.
     */
    private static final int DIGIT_MASK = (1 << DIGIT_BITS) - 1;
    /**
     * The number of digits per element.
     */
    private static final int DIGITS_PER_ELEMENT = Integer.SIZE / DIGIT_BITS;

    
    private IntArraySort() {
        // utility class
    }

    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using quicksort.
     *
     * <p>The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley
     * and M. Douglas McIlroy, &ldquo;Engineering a Sort Function&rdquo;,
     * <i>Software: Practice and Experience</i>, 23(11), pages 1249&minus;1265,
     * 1993.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     *
     */
    public static void quickSort(int[] array, int begin, int end, IntComparator comp) {
        int len = end - begin;
        // Selection sort on smallest arrays
        if (len < SMALL) {
            selectionSort(array, begin, end, comp);
            return;
    }
        // Choose a partition element, v
        int m = begin + len / 2; // Small arrays, middle element
        if (len > SMALL) {
            int l = begin;
            int n = end - 1;
            if (len > MEDIUM) { // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = med3(array, l, l + s, l + 2 * s, comp);
                m = med3(array, m - s, m, m + s, comp);
                n = med3(array, n - 2 * s, n - s, n, comp);
            }
            m = med3(array, l, m, n, comp); // Mid-size, med of 3
        }
        int v = array[ m];
        // Establish Invariant: v* (<v)* (>v)* v*
        int a = begin, b = a, c = end - 1, d = c;
        while (true) {
            int comparison;
            while (b <= c && (comparison = comp.compare(array[ b], v)) <= 0) {
                if (comparison == 0) {
                    swap(array, a++, b);
                }
                b++;
            }
            while (c >= b && (comparison = comp.compare(array[ c], v)) >= 0) {
                if (comparison == 0) {
                    swap(array, c, d--);
                }
                c--;
            }
            if (b > c) {
                break;
            }
            swap(array, b++, c--);
        }
        // Swap partition elements back to middle
        int s, n = end;
        s = Math.min(a - begin, b - a);
        vecSwap(array, begin, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vecSwap(array, b, n - s, s);
        // Recursively sort non-partition-elements
        if ((s = b - a) > 1) {
            quickSort(array, begin, begin + s, comp);
        }
        if ((s = d - c) > 1) {
            quickSort(array, n - s, n, comp);
        }
    }

    /**
     * Sorts an array according to the order induced by the specified comparator
     * using quicksort.
     *
     * <p>The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley
     * and M. Douglas McIlroy, &ldquo;Engineering a Sort Function&rdquo;,
     * <i>Software: Practice and Experience</i>, 23(11), pages 1249&minus;1265,
     * 1993.
     *
     * @param array the array to be sorted.
     * @param comp the comparator to determine the sorting order.
     *
     */
    public static void quickSort(int[] array, IntComparator comp) {
        quickSort(array, 0, array.length, comp);
    }
    
    
    /**
     * Sorts an array according to the natural ascending order using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>a</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     */
    public static void mergeSort(int[] array) {
        mergeSort(array, 0, array.length);
    }
    
    /**
     * Sorts the specified range of elements according to the natural ascending
     * order using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>a</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     */
    public static void mergeSort(int[] array, int begin, int end) {
        mergeSort(array, begin, end, array.clone());
    }

    /**
     * Sorts the specified range of elements according to the natural ascending
     * order using mergesort, using a given support array.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. Moreover, no support arrays will be
     * allocated.
     *
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param supp a support array containing at least <code>to</code> elements.
     */
    private static void mergeSort(int[] array, int begin, int end, int supp[]) {
        mergeSort(array, begin, end, Integer::compare, supp);
    }
    
    /**
     * Sorts an array according to the order induced by the specified comparator
     * using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>a</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param comp the comparator to determine the sorting order.
     */
    public static void mergeSort(int[] array, IntComparator comp) {
        mergeSort(array, 0, array.length, comp);
    }

    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using mergesort.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. An array as large as
     * <code>a</code> will be allocated by this method.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     */
    public static void mergeSort(int[] array, int begin, int end, IntComparator comp) {
        mergeSort(array, begin, end, comp, array.clone());
    }


    /**
     * Sorts the specified range of elements according to the order induced by
     * the specified comparator using mergesort, using a given support array.
     *
     * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not
     * be reordered as a result of the sort. Moreover, no support arrays will be
     * allocated.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     * @param comp the comparator to determine the sorting order.
     * @param supp a support array containing at least <code>to</code> elements.
     */
    private static void mergeSort(int[] array, int begin, int end, IntComparator comp, int supp[]) {
        int len = end - begin;
        // Insertion sort on smallest arrays
        if (len < SMALL) {
            insertionSort(array, begin, end, comp);
            return;
        }
        // Recursively sort halves of a into supp
        int mid = (begin + end) >>> 1;
        mergeSort(supp, begin, mid, comp, array);
        mergeSort(supp, mid, end, comp, array);
        // If list is already sorted, just copy from supp to a.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (comp.compare(supp[ mid - 1], supp[ mid]) <= 0) {
            System.arraycopy(supp, begin, array, begin, len);
            return;
        }
        // Merge sorted halves (now in supp) into a
        for (int i = begin, p = begin, q = mid; i < end; i++) {
            if (q >= end || p < mid && comp.compare(supp[ p], supp[ q]) <= 0) {
                array[ i] = supp[ p++];
            } else {
                array[ i] = supp[ q++];
            }
        }
    }

    /**
     * This method fixes negative numbers so that the combination
     * exponent/significand is lexicographically sorted.
     */
    /**
     * Sorts the specified array using radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the array to be sorted.
     *
     * @param array the array to be sorted.
     */
    public static void radixSort(int[] array) {
        radixSort(array, 0, array.length);
    }

    /**
     * Sorts the specified array using radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the array to be sorted.
     *
     * @param array the array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     */
    @SuppressWarnings("MismatchedReadAndWriteOfArray")
    public static void radixSort(int[] array, int begin, int end) {
        int maxLevel = DIGITS_PER_ELEMENT - 1;
        int stackSize = ((1 << DIGIT_BITS) - 1) * (DIGITS_PER_ELEMENT - 1) + 1;
        int[] offsetStack = new int[stackSize];
        int offsetPos = 0;
        int[] lengthStack = new int[stackSize];
        int lengthPos = 0;
        int[] levelStack = new int[stackSize];
        int levelPos = 0;
        offsetStack[ offsetPos++] = begin;
        lengthStack[ lengthPos++] = end - begin;
        levelStack[ levelPos++] = 0;
        int[] count = new int[1 << DIGIT_BITS];
        int[] pos = new int[1 << DIGIT_BITS];
        byte[] digit = new byte[end - begin];
        while (offsetPos > 0) {
            int first = offsetStack[ --offsetPos];
            int length = lengthStack[ --lengthPos];
            int level = levelStack[ --levelPos];
            int signMask = level % DIGITS_PER_ELEMENT == 0 ? 1 << DIGIT_BITS - 1 : 0;
            if (length < MEDIUM) {
                selectionSort(array, first, first + length);
                continue;
            }
            int shift = (DIGITS_PER_ELEMENT - 1 - level % DIGITS_PER_ELEMENT) * DIGIT_BITS; // This is the shift that extract the right byte from a key
            // Count keys.
            for (int i = length; i-- != 0;) {
                digit[ i] = (byte) ((((array[ first + i]) >>> shift) & DIGIT_MASK) ^ signMask);
            }
            for (int i = length; i-- != 0;) {
                count[ digit[ i] & 0xFF]++;
            }
            // Compute cumulative distribution and push non-singleton keys on stack.
            int lastUsed = -1;
            for (int i = 0, p = 0; i < 1 << DIGIT_BITS; i++) {
                if (count[ i] != 0) {
                    lastUsed = i;
                    if (level < maxLevel && count[ i] > 1) {
                        //System.err.println( " Pushing " + new StackEntry( first + pos[ i - 1 ], first + pos[ i ], level + 1 ) );
                        offsetStack[ offsetPos++] = p + first;
                        lengthStack[ lengthPos++] = count[ i];
                        levelStack[ levelPos++] = level + 1;
                    }
                }
                pos[ i] = (p += count[ i]);
            }
            // When all slots are OK, the last slot is necessarily OK.
            int iend = length - count[ lastUsed];
            count[ lastUsed] = 0;
            // i moves through the start of each block
            for (int i = 0, c, d; i < iend; i += count[ c], count[ c] = 0) {
                int t = array[ i + first];
                c = digit[ i] & 0xFF;
                while ((d = --pos[ c]) > i) {
                    int z = t;
                    int zz = c;
                    t = array[ d + first];
                    c = digit[ d] & 0xFF;
                    array[ d + first] = z;
                    digit[ d] = (byte) zz;
                }
                array[ i + first] = t;
            }
        }
    }

    /**
     * Sorts the specified pair of arrays lexicographically using radix sort.
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implements a <em>lexicographical</em> sorting of the
     * arguments. Pairs of elements in the same position in the two provided
     * arrays will be considered a single key, and permuted accordingly. In the
     * end, either
     * <code>a[ i ] < a[ i + 1 ]</code> or
     * <code>a[ i ] == a[ i + 1 ]</code> and
     * <code>b[ i ] <= b[ i + 1 ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the arrays to be sorted.
     *
     * @param array1 the first array to be sorted.
     * @param array2 the second array to be sorted.
     */
    public static void radixSort(int[] array1, int[] array2) {
        radixSort(array1, array2, 0, array1.length);
    }

    /**
     * Sorts the specified pair of arrays lexicographically using radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implements a <em>lexicographical</em> sorting of the
     * arguments. Pairs of elements in the same position in the two provided
     * arrays will be considered a single key, and permuted accordingly. In the
     * end, either
     * <code>a[ i ] < a[ i + 1 ]</code> or
     * <code>a[ i ] == a[ i + 1 ]</code> and
     * <code>b[ i ] <= b[ i + 1 ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the arrays to be sorted.
     *
     * @param array1 the first array to be sorted.
     * @param array2 the second array to be sorted.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     */
    @SuppressWarnings("MismatchedReadAndWriteOfArray")
    public static void radixSort(int[] array1, int[] array2, int begin, int end) {
        int layers = 2;
        if (array1.length != array2.length) {
            throw new IllegalArgumentException("Array size mismatch.");
        }
        int maxLevel = DIGITS_PER_ELEMENT * layers - 1;
        int stackSize = ((1 << DIGIT_BITS) - 1) * (layers * DIGITS_PER_ELEMENT - 1) + 1;
        int[] offsetStack = new int[stackSize];
        int offsetPos = 0;
        int[] lengthStack = new int[stackSize];
        int lengthPos = 0;
        int[] levelStack = new int[stackSize];
        int levelPos = 0;
        offsetStack[ offsetPos++] = begin;
        lengthStack[ lengthPos++] = end - begin;
        levelStack[ levelPos++] = 0;
        int[] count = new int[1 << DIGIT_BITS];
        int[] pos = new int[1 << DIGIT_BITS];
        byte[] digit = new byte[end - begin];
        while (offsetPos > 0) {
            int first = offsetStack[ --offsetPos];
            int length = lengthStack[ --lengthPos];
            int level = levelStack[ --levelPos];
            int signMask = level % DIGITS_PER_ELEMENT == 0 ? 1 << DIGIT_BITS - 1 : 0;
            if (length < MEDIUM) {
                selectionSort(array1, array2, first, first + length);
                continue;
            }
            int[] k = level < DIGITS_PER_ELEMENT ? array1 : array2; // This is the key array
            int shift = (DIGITS_PER_ELEMENT - 1 - level % DIGITS_PER_ELEMENT) * DIGIT_BITS; // This is the shift that extract the right byte from a key
            // Count keys.
            for (int i = length; i-- != 0;) {
                digit[ i] = (byte) ((((k[ first + i]) >>> shift) & DIGIT_MASK) ^ signMask);
            }
            for (int i = length; i-- != 0;) {
                count[ digit[ i] & 0xFF]++;
            }
            // Compute cumulative distribution and push non-singleton keys on stack.
            int lastUsed = -1;
            for (int i = 0, p = 0; i < 1 << DIGIT_BITS; i++) {
                if (count[ i] != 0) {
                    lastUsed = i;
                    if (level < maxLevel && count[ i] > 1) {
                        offsetStack[ offsetPos++] = p + first;
                        lengthStack[ lengthPos++] = count[ i];
                        levelStack[ levelPos++] = level + 1;
                    }
                }
                pos[ i] = (p += count[ i]);
            }
            // When all slots are OK, the last slot is necessarily OK.
            int iend = length - count[ lastUsed];
            count[ lastUsed] = 0;
            // i moves through the start of each block
            for (int i = 0, c, d; i < iend; i += count[ c], count[ c] = 0) {
                int t = array1[ i + first];
                int u = array2[ i + first];
                c = digit[ i] & 0xFF;
                while ((d = --pos[ c]) > i) {
                    int z = t;
                    int zz = c;
                    t = array1[ d + first];
                    array1[ d + first] = z;
                    z = u;
                    u = array2[ d + first];
                    array2[ d + first] = z;
                    c = digit[ d] & 0xFF;
                    digit[ d] = (byte) zz;
                }
                array1[ i + first] = t;
                array2[ i + first] = u;
            }
        }
    }
        
    /**
     * Sorts the specified array using indirect radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implement an <em>indirect</em> sort. The elements of
     * <code>perm</code> (which must be exactly the numbers in the interval
     * <code>[0..perm.length)</code>) will be permuted so that
     * <code>a[ perm[ i ] ] <= a[ perm[ i + 1 ] ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort (unstable)
     * or mergesort (stable) already at small sizes (say, more than 10000
     * elements), but it can only sort in ascending order. It will allocate a
     * support array of bytes with the same number of elements as the array to
     * be sorted, and, in the stable case, a further support array as large as
     * <code>perm</code> (note that the stable version is slightly faster).
     *
     * @param perm a permutation array indexing <code>a</code>.
     * @param array the array to be sorted.
     * @param stable whether the sorting algorithm should be stable.
     */
    public static void radixSortIndirect(int[] perm, int[] array, boolean stable) {
        radixSortIndirect(perm, array, 0, perm.length, stable);
    }

    /**
     * Sorts the specified array using indirect radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implement an <em>indirect</em> sort. The elements of
     * <code>perm</code> (which must be exactly the numbers in the interval
     * <code>[0..perm.length)</code>) will be permuted so that
     * <code>a[ perm[ i ] ] <= a[ perm[ i + 1 ] ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort (unstable)
     * or mergesort (stable) already at small sizes (say, more than 10000
     * elements), but it can only sort in ascending order. It will allocate a
     * support array of bytes with the same number of elements as the array to
     * be sorted, and, in the stable case, a further support array as large as
     * <code>perm</code> (note that the stable version is slightly faster).
     *
     * @param perm a permutation array indexing <code>a</code>.
     * @param array the array to be sorted.
     * @param begin the index of the first element of <code>perm</code>
     * (inclusive) to be permuted.
     * @param end the index of the last element of <code>perm</code> (exclusive)
     * to be permuted.
     * @param stable whether the sorting algorithm should be stable.
     */
    @SuppressWarnings("MismatchedReadAndWriteOfArray")
    public static void radixSortIndirect(int[] perm, int[] array, int begin, int end, boolean stable) {
        int maxLevel = DIGITS_PER_ELEMENT - 1;
        int stackSize = ((1 << DIGIT_BITS) - 1) * (DIGITS_PER_ELEMENT - 1) + 1;
        int[] offsetStack = new int[stackSize];
        int offsetPos = 0;
        int[] lengthStack = new int[stackSize];
        int lengthPos = 0;
        int[] levelStack = new int[stackSize];
        int levelPos = 0;
        offsetStack[ offsetPos++] = begin;
        lengthStack[ lengthPos++] = end - begin;
        levelStack[ levelPos++] = 0;
        int[] count = new int[1 << DIGIT_BITS];
        int[] pos = stable ? null : new int[1 << DIGIT_BITS];
        int[] support = stable ? new int[perm.length] : null;
        byte[] digit = new byte[end - begin];
        while (offsetPos > 0) {
            int first = offsetStack[ --offsetPos];
            int length = lengthStack[ --lengthPos];
            int level = levelStack[ --levelPos];
            int signMask = level % DIGITS_PER_ELEMENT == 0 ? 1 << DIGIT_BITS - 1 : 0;
            if (length < MEDIUM) {
                insertionSortIndirect(perm, array, first, first + length);
                continue;
            }
            int shift = (DIGITS_PER_ELEMENT - 1 - level % DIGITS_PER_ELEMENT) * DIGIT_BITS; // This is the shift that extract the right byte from a key
            // Count keys.
            for (int i = length; i-- != 0;) {
                digit[ i] = (byte) ((((array[ perm[ first + i]]) >>> shift) & DIGIT_MASK) ^ signMask);
            }
            for (int i = length; i-- != 0;) {
                count[ digit[ i] & 0xFF]++;
            }
            // Compute cumulative distribution and push non-singleton keys on stack.
            int lastUsed = -1;
            for (int i = 0, p = 0; i < 1 << DIGIT_BITS; i++) {
                if (count[ i] != 0) {
                    lastUsed = i;
                    if (level < maxLevel && count[ i] > 1) {
                        offsetStack[ offsetPos++] = p + first;
                        lengthStack[ lengthPos++] = count[ i];
                        levelStack[ levelPos++] = level + 1;
                    }
                }
                if (stable) {
                    count[ i] = p += count[ i];
                } else {
                    pos[ i] = (p += count[ i]);
                }
            }
            if (stable) {
                for (int i = length; i-- != 0;) {
                    support[ --count[ digit[ i] & 0xFF]] = perm[ first + i];
                }
                System.arraycopy(support, 0, perm, first, length);
                ArrayUtils.fill(count, 0);
            } else {
                // When all slots are OK, the last slot is necessarily OK.
                int iend = length - count[ lastUsed];
                count[ lastUsed] = 0;
                // i moves through the start of each block
                for (int i = 0, c, d; i < iend; i += count[ c], count[ c] = 0) {
                    int t = perm[ i + first];
                    c = digit[ i] & 0xFF;
                    while ((d = --pos[ c]) > i) {
                        int z = t;
                        int zz = c;
                        t = perm[ d + first];
                        c = digit[ d] & 0xFF;
                        perm[ d + first] = z;
                        digit[ d] = (byte) zz;
                    }
                    perm[ i + first] = t;
                }
            }
        }
    }

    /**
     * Sorts the specified pair of arrays lexicographically using indirect radix
     * sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implement an <em>indirect</em> sort. The elements of
     * <code>perm</code> (which must be exactly the numbers in the interval
     * <code>[0..perm.length)</code>) will be permuted so that
     * <code>a[ perm[ i ] ] <= a[ perm[ i + 1 ] ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort (unstable)
     * or mergesort (stable) already at small sizes (say, more than 10000
     * elements), but it can only sort in ascending order. It will allocate a
     * support array of bytes with the same number of elements as the array to
     * be sorted, and, in the stable case, a further support array as large as
     * <code>perm</code> (note that the stable version is slightly faster).
     *
     * @param perm a permutation array indexing <code>a</code>.
     * @param array1 the array to be sorted.
     * @param array2 the second array to be sorted.
     * @param stable whether the sorting algorithm should be stable.
     */
    public static void radixSortIndirect(int[] perm, int[] array1, int[] array2, boolean stable) {
        radixSortIndirect(perm, array1, array2, 0, perm.length, stable);
    }

    /**
     * Sorts the specified pair of arrays lexicographically using indirect radix
     * sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implement an <em>indirect</em> sort. The elements of
     * <code>perm</code> (which must be exactly the numbers in the interval
     * <code>[0..perm.length)</code>) will be permuted so that
     * <code>a[ perm[ i ] ] <= a[ perm[ i + 1 ] ]</code>.
     *
     * <p>This implementation is significantly faster than quicksort (unstable)
     * or mergesort (stable) already at small sizes (say, more than 10000
     * elements), but it can only sort in ascending order. It will allocate a
     * support array of bytes with the same number of elements as the array to
     * be sorted, and, in the stable case, a further support array as large as
     * <code>perm</code> (note that the stable version is slightly faster).
     *
     * @param perm a permutation array indexing <code>a</code>.
     * @param array1 the array to be sorted.
     * @param array2 the second array to be sorted.
     * @param begin the index of the first element of <code>perm</code>
     * (inclusive) to be permuted.
     * @param end the index of the last element of <code>perm</code> (exclusive)
     * to be permuted.
     * @param stable whether the sorting algorithm should be stable.
     */
    @SuppressWarnings("MismatchedReadAndWriteOfArray")
    public static void radixSortIndirect(int[] perm, int[] array1, int[] array2, int begin, int end, boolean stable) {
        int layers = 2;
        if (array1.length != array2.length) {
            throw new IllegalArgumentException("Array size mismatch.");
        }
        int maxLevel = DIGITS_PER_ELEMENT * layers - 1;
        int stackSize = ((1 << DIGIT_BITS) - 1) * (layers * DIGITS_PER_ELEMENT - 1) + 1;
        int[] offsetStack = new int[stackSize];
        int offsetPos = 0;
        int[] lengthStack = new int[stackSize];
        int lengthPos = 0;
        int[] levelStack = new int[stackSize];
        int levelPos = 0;
        offsetStack[ offsetPos++] = begin;
        lengthStack[ lengthPos++] = end - begin;
        levelStack[ levelPos++] = 0;
        int[] count = new int[1 << DIGIT_BITS];
        int[] pos = stable ? null : new int[1 << DIGIT_BITS];
        int[] support = stable ? new int[perm.length] : null;
        byte[] digit = new byte[end - begin];
        while (offsetPos > 0) {
            int first = offsetStack[ --offsetPos];
            int length = lengthStack[ --lengthPos];
            int level = levelStack[ --levelPos];
            int signMask = level % DIGITS_PER_ELEMENT == 0 ? 1 << DIGIT_BITS - 1 : 0;
            if (length < MEDIUM) {
                insertionSortIndirect(perm, array1, array2, first, first + length);
                continue;
            }
            int[] k = level < DIGITS_PER_ELEMENT ? array1 : array2; // This is the key array
            int shift = (DIGITS_PER_ELEMENT - 1 - level % DIGITS_PER_ELEMENT) * DIGIT_BITS; // This is the shift that extract the right byte from a key
            // Count keys.
            for (int i = length; i-- != 0;) {
                digit[ i] = (byte) ((((k[ perm[ first + i]]) >>> shift) & DIGIT_MASK) ^ signMask);
            }
            for (int i = length; i-- != 0;) {
                count[ digit[ i] & 0xFF]++;
            }
            // Compute cumulative distribution and push non-singleton keys on stack.
            int lastUsed = -1;
            for (int i = 0, p = 0; i < 1 << DIGIT_BITS; i++) {
                if (count[ i] != 0) {
                    lastUsed = i;
                    if (level < maxLevel && count[ i] > 1) {
                        offsetStack[ offsetPos++] = p + first;
                        lengthStack[ lengthPos++] = count[ i];
                        levelStack[ levelPos++] = level + 1;
                    }
                }
                if (stable) {
                    count[ i] = p += count[ i];
                } else {
                    pos[ i] = (p += count[ i]);
                }
            }
            if (stable) {
                for (int i = length; i-- != 0;) {
                    support[ --count[ digit[ i] & 0xFF]] = perm[ first + i];
                }
                System.arraycopy(support, 0, perm, first, length);
                ArrayUtils.fill(count, 0);
            } else {
                // When all slots are OK, the last slot is necessarily OK.
                int iend = length - count[ lastUsed];
                count[ lastUsed] = 0;
                // i moves through the start of each block
                for (int i = 0, c, d; i < iend; i += count[ c], count[ c] = 0) {
                    int t = perm[ i + first];
                    c = digit[ i] & 0xFF;
                    while ((d = --pos[ c]) > i) {
                        int z = t;
                        int zz = c;
                        t = perm[ d + first];
                        c = digit[ d] & 0xFF;
                        perm[ d + first] = z;
                        digit[ d] = (byte) zz;
                    }
                    perm[ i + first] = t;
                }
            }
        }
    }

    /**
     * Sorts the specified array of arrays lexicographically using radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implements a <em>lexicographical</em> sorting of the
     * provided arrays. Tuples of elements in the same position will be
     * considered a single key, and permuted accordingly.
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the arrays to be sorted.
     *
     * @param array an array containing arrays of equal length to be sorted
     * lexicographically in parallel.
     */
    public static void lexicalSort(int[][] array) {
        IntArraySort.lexicalSort(array, 0, array[ 0].length);
    }

    /**
     * Sorts the specified array of arrays lexicographically using radix sort.
     *
     * <p>The sorting algorithm is a tuned radix sort adapted from Peter M.
     * McIlroy, Keith Bostic and M. Douglas McIlroy, &ldquo;Engineering radix
     * sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993), and
     * further improved using the digit-oracle idea described by Juha
     * K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort
     * for strings&rdquo;,
     * <i>String Processing and Information Retrieval, 15th International
     * Symposium</i>, volume 5280 of Lecture Notes in Computer Science, pages
     * 3&minus;14, Springer (2008).
     *
     * <p>This method implements a <em>lexicographical</em> sorting of the
     * provided arrays. Tuples of elements in the same position will be
     * considered a single key, and permuted accordingly.
     *
     * <p>This implementation is significantly faster than quicksort already at
     * small sizes (say, more than 10000 elements), but it can only sort in
     * ascending order. It will allocate a support array of bytes with the same
     * number of elements as the arrays to be sorted.
     *
     * @param array an array containing arrays of equal length to be sorted
     * lexicographically in parallel.
     * @param begin the index of the first element (inclusive) to be sorted.
     * @param end the index of the last element (exclusive) to be sorted.
     */
    @SuppressWarnings("MismatchedReadAndWriteOfArray")
    public static void lexicalSort(int[][] array, int begin, int end) {
        int layers = array.length;
        int maxLevel = DIGITS_PER_ELEMENT * layers - 1;
        for (int p = layers, l = array[ 0].length; p-- != 0;) {
            if (array[ p].length != l) {
                throw new IllegalArgumentException("The array of index " + p + " has not the same length of the array of index 0.");
            }
        }
        int stackSize = ((1 << DIGIT_BITS) - 1) * (layers * DIGITS_PER_ELEMENT - 1) + 1;
        int[] offsetStack = new int[stackSize];
        int offsetPos = 0;
        int[] lengthStack = new int[stackSize];
        int lengthPos = 0;
        int[] levelStack = new int[stackSize];
        int levelPos = 0;
        offsetStack[ offsetPos++] = begin;
        lengthStack[ lengthPos++] = end - begin;
        levelStack[ levelPos++] = 0;
        int[] count = new int[1 << DIGIT_BITS];
        int[] pos = new int[1 << DIGIT_BITS];
        byte[] digit = new byte[end - begin];
        int[] t = new int[layers];
        while (offsetPos > 0) {
            int first = offsetStack[ --offsetPos];
            int length = lengthStack[ --lengthPos];
            int level = levelStack[ --levelPos];
            int signMask = level % DIGITS_PER_ELEMENT == 0 ? 1 << DIGIT_BITS - 1 : 0;
            if (length < MEDIUM) {
                selectionSort(array, first, first + length, level);
                continue;
            }
            int[] k = array[ level / DIGITS_PER_ELEMENT]; // This is the key array
            int shift = (DIGITS_PER_ELEMENT - 1 - level % DIGITS_PER_ELEMENT) * DIGIT_BITS; // This is the shift that extract the right byte from a key
            // Count keys.
            for (int i = length; i-- != 0;) {
                digit[ i] = (byte) (((k[ first + i]) >>> shift & DIGIT_MASK) ^ signMask);
            }
            for (int i = length; i-- != 0;) {
                count[ digit[ i] & 0xFF]++;
            }
            // Compute cumulative distribution and push non-singleton keys on stack.
            int lastUsed = -1;
            for (int i = 0, p = 0; i < 1 << DIGIT_BITS; i++) {
                if (count[ i] != 0) {
                    lastUsed = i;
                    if (level < maxLevel && count[ i] > 1) {
                        offsetStack[ offsetPos++] = p + first;
                        lengthStack[ lengthPos++] = count[ i];
                        levelStack[ levelPos++] = level + 1;
                    }
                }
                pos[ i] = (p += count[ i]);
            }
            // When all slots are OK, the last slot is necessarily OK.
            int iend = length - count[ lastUsed];
            count[ lastUsed] = 0;
            // i moves through the start of each block
            for (int i = 0, c, d; i < iend; i += count[ c], count[ c] = 0) {
                for (int p = layers; p-- != 0;) {
                    t[ p] = array[ p][ i + first];
                }
                c = digit[ i] & 0xFF;
                while ((d = --pos[ c]) > i) {
                    for (int p = layers; p-- != 0;) {
                        int u = t[ p];
                        t[ p] = array[ p][ d + first];
                        array[ p][ d + first] = u;
                    }
                    int zz = c;
                    c = digit[ d] & 0xFF;
                    digit[ d] = (byte) zz;
                }
                for (int p = layers; p-- != 0;) {
                    array[ p][ i + first] = t[ p];
                }
            }
        }
    }
    
    
    private static void selectionSort(int[][] array, int from, int to, int level) {
        int layers = array.length;
        int firstLayer = level / DIGITS_PER_ELEMENT;
        for (int i = from; i < to - 1; i++) {
            int m = i;
            for (int j = i + 1; j < to; j++) {
                for (int p = firstLayer; p < layers; p++) {
                    if (array[ p][ j] < array[ p][ m]) {
                        m = j;
                        break;
                    } else if (array[ p][ j] > array[ p][ m]) {
                        break;
                    }
                }
            }
            if (m != i) {
                for (int p = layers; p-- != 0;) {
                    int u = array[ p][ i];
                    array[ p][ i] = array[ p][ m];
                    array[ p][ m] = u;
                }
            }
        }
    }
    
    private static void selectionSort(int[] array, int from, int to, IntComparator comp) {
        for (int i = from; i < to - 1; i++) {
            int m = i;
            for (int j = i + 1; j < to; j++) {
                if (comp.compare(array[ j], array[ m]) < 0) {
                    m = j;
                }
            }
            if (m != i) {
                int u = array[ i];
                array[ i] = array[ m];
                array[ m] = u;
            }
        }
    }
    
    

    @SuppressWarnings("unchecked")
    private static void selectionSort(int[] array, int from, int to) {
        for (int i = from; i < to - 1; i++) {
            int m = i;
            for (int j = i + 1; j < to; j++) {
                if (((array[ j]) < (array[ m]))) {
                    m = j;
                }
            }
            if (m != i) {
                int u = array[ i];
                array[ i] = array[ m];
                array[ m] = u;
            }
        }
    }
    
    private static void selectionSort(int[] array1, int[] array2, int from, int to) {
        for (int i = from; i < to - 1; i++) {
            int m = i;
            for (int j = i + 1; j < to; j++) {
                if (array1[ j] < array1[ m] || array1[ j] == array1[ m] && array2[ j] < array2[ m]) {
                    m = j;
                }
            }
            if (m != i) {
                int t = array1[ i];
                array1[ i] = array1[ m];
                array1[ m] = t;
                t = array2[ i];
                array2[ i] = array2[ m];
                array2[ m] = t;
            }
        }
    }

    private static void insertionSort(int[] array, int from, int to, IntComparator comp) {
        for (int i = from; ++i < to;) {
            int t = array[ i];
            int j = i;
            for (int u = array[ j - 1]; comp.compare(t, u) < 0; u = array[ --j - 1]) {
                array[ j] = u;
                if (from == j - 1) {
                    --j;
                    break;
                }
            }
            array[ j] = t;
        }
    }

    private static void insertionSortIndirect(int[] perm, int[] a, int[] b, int from, int to) {
        for (int i = from; ++i < to;) {
            int t = perm[ i];
            int j = i;
            for (int u = perm[ j - 1]; ((a[ t]) < (a[ u])) || ((a[ t]) == (a[ u])) && ((b[ t]) < (b[ u])); u = perm[ --j - 1]) {
                perm[ j] = u;
                if (from == j - 1) {
                    --j;
                    break;
                }
            }
            perm[ j] = t;
        }
    }
    
    private static void insertionSortIndirect(int[] perm, int[] array, int from, int to) {
        for (int i = from; ++i < to;) {
            int t = perm[ i];
            int j = i;
            for (int u = perm[ j - 1]; ((array[ t]) < (array[ u])); u = perm[ --j - 1]) {
                perm[ j] = u;
                if (from == j - 1) {
                    --j;
                    break;
                }
            }
            perm[ j] = t;
        }
    }

    

    
    
    private static int med3(int array[], int a, int b, int c, IntComparator comp) {
        int ab = comp.compare(array[ a], array[ b]);
        int ac = comp.compare(array[ a], array[ c]);
        int bc = comp.compare(array[ b], array[ c]);
        return (ab < 0
                ? (bc < 0 ? b : ac < 0 ? c : a)
                : (bc > 0 ? b : ac > 0 ? c : a));
    }
    
    private static void vecSwap(int[] array, int a, int b, int n) {
        for (int i = 0; i < n; i++, a++, b++) {
            swap(array, a, b);
        }
    }
    
    private static void swap(int array[], int a, int b) {
        int t = array[ a];
        array[ a] = array[ b];
        array[ b] = t;
    }
    
}
