// 
// Decompiled by Procyon v0.6.0
// 

package it.unimi.dsi.fastutil.shorts;

import java.util.concurrent.RecursiveAction;
import java.io.Serializable;
import java.util.Random;
import it.unimi.dsi.fastutil.longs.LongBigArrays;
import it.unimi.dsi.fastutil.bytes.ByteBigArrays;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.ForkJoinPool;
import java.util.Arrays;
import it.unimi.dsi.fastutil.BigArrays;
import it.unimi.dsi.fastutil.Hash;

public final class ShortBigArrays
{
    public static final short[][] EMPTY_BIG_ARRAY;
    public static final short[][] DEFAULT_EMPTY_BIG_ARRAY;
    public static final Hash.Strategy HASH_STRATEGY;
    private static final int QUICKSORT_NO_REC = 7;
    private static final int PARALLEL_QUICKSORT_NO_FORK = 8192;
    private static final int MEDIUM = 40;
    private static final int DIGIT_BITS = 8;
    private static final int DIGIT_MASK = 255;
    private static final int DIGITS_PER_ELEMENT = 2;
    private static final int RADIXSORT_NO_REC = 1024;
    
    private ShortBigArrays() {
    }
    
    @Deprecated
    public static short get(final short[][] array, final long index) {
        return array[BigArrays.segment(index)][BigArrays.displacement(index)];
    }
    
    @Deprecated
    public static void set(final short[][] array, final long index, final short value) {
        array[BigArrays.segment(index)][BigArrays.displacement(index)] = value;
    }
    
    @Deprecated
    public static void swap(final short[][] array, final long first, final long second) {
        final short t = array[BigArrays.segment(first)][BigArrays.displacement(first)];
        array[BigArrays.segment(first)][BigArrays.displacement(first)] = array[BigArrays.segment(second)][BigArrays.displacement(second)];
        array[BigArrays.segment(second)][BigArrays.displacement(second)] = t;
    }
    
    @Deprecated
    public static void add(final short[][] array, final long index, final short incr) {
        final short[] array2 = array[BigArrays.segment(index)];
        final int displacement = BigArrays.displacement(index);
        array2[displacement] += incr;
    }
    
    @Deprecated
    public static void mul(final short[][] array, final long index, final short factor) {
        final short[] array2 = array[BigArrays.segment(index)];
        final int displacement = BigArrays.displacement(index);
        array2[displacement] *= factor;
    }
    
    @Deprecated
    public static void incr(final short[][] array, final long index) {
        final short[] array2 = array[BigArrays.segment(index)];
        final int displacement = BigArrays.displacement(index);
        ++array2[displacement];
    }
    
    @Deprecated
    public static void decr(final short[][] array, final long index) {
        final short[] array2 = array[BigArrays.segment(index)];
        final int displacement = BigArrays.displacement(index);
        --array2[displacement];
    }
    
    @Deprecated
    public static long length(final short[][] array) {
        final int length = array.length;
        return (length == 0) ? 0L : (BigArrays.start(length - 1) + array[length - 1].length);
    }
    
    @Deprecated
    public static void copy(final short[][] srcArray, final long srcPos, final short[][] destArray, final long destPos, final long length) {
        BigArrays.copy(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static void copyFromBig(final short[][] srcArray, final long srcPos, final short[] destArray, final int destPos, final int length) {
        BigArrays.copyFromBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    @Deprecated
    public static void copyToBig(final short[] srcArray, final int srcPos, final short[][] destArray, final long destPos, final long length) {
        BigArrays.copyToBig(srcArray, srcPos, destArray, destPos, length);
    }
    
    public static short[][] newBigArray(final long length) {
        if (length == 0L) {
            return ShortBigArrays.EMPTY_BIG_ARRAY;
        }
        BigArrays.ensureLength(length);
        final int baseLength = (int)(length + 134217727L >>> 27);
        final short[][] base = new short[baseLength][];
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            for (int i = 0; i < baseLength - 1; ++i) {
                base[i] = new short[134217728];
            }
            base[baseLength - 1] = new short[residual];
        }
        else {
            for (int i = 0; i < baseLength; ++i) {
                base[i] = new short[134217728];
            }
        }
        return base;
    }
    
    @Deprecated
    public static short[][] wrap(final short[] array) {
        return BigArrays.wrap(array);
    }
    
    @Deprecated
    public static short[][] ensureCapacity(final short[][] array, final long length) {
        return ensureCapacity(array, length, length(array));
    }
    
    @Deprecated
    public static short[][] forceCapacity(final short[][] array, final long length, final long preserve) {
        return BigArrays.forceCapacity(array, length, preserve);
    }
    
    @Deprecated
    public static short[][] ensureCapacity(final short[][] array, final long length, final long preserve) {
        return (length > length(array)) ? forceCapacity(array, length, preserve) : array;
    }
    
    @Deprecated
    public static short[][] grow(final short[][] array, final long length) {
        final long oldLength = length(array);
        return (length > oldLength) ? grow(array, length, oldLength) : array;
    }
    
    @Deprecated
    public static short[][] grow(final short[][] array, final long length, final long preserve) {
        final long oldLength = length(array);
        return (length > oldLength) ? ensureCapacity(array, Math.max(oldLength + (oldLength >> 1), length), preserve) : array;
    }
    
    @Deprecated
    public static short[][] trim(final short[][] array, final long length) {
        BigArrays.ensureLength(length);
        final long oldLength = length(array);
        if (length >= oldLength) {
            return array;
        }
        final int baseLength = (int)(length + 134217727L >>> 27);
        final short[][] base = Arrays.copyOf(array, baseLength);
        final int residual = (int)(length & 0x7FFFFFFL);
        if (residual != 0) {
            base[baseLength - 1] = ShortArrays.trim(base[baseLength - 1], residual);
        }
        return base;
    }
    
    @Deprecated
    public static short[][] setLength(final short[][] array, final long length) {
        return BigArrays.setLength(array, length);
    }
    
    @Deprecated
    public static short[][] copy(final short[][] array, final long offset, final long length) {
        return BigArrays.copy(array, offset, length);
    }
    
    @Deprecated
    public static short[][] copy(final short[][] array) {
        return BigArrays.copy(array);
    }
    
    @Deprecated
    public static void fill(final short[][] array, final short value) {
        int i = array.length;
        while (i-- != 0) {
            Arrays.fill(array[i], value);
        }
    }
    
    @Deprecated
    public static void fill(final short[][] array, final long from, final long to, final short value) {
        BigArrays.fill(array, from, to, value);
    }
    
    @Deprecated
    public static boolean equals(final short[][] a1, final short[][] a2) {
        return BigArrays.equals(a1, a2);
    }
    
    @Deprecated
    public static String toString(final short[][] a) {
        return BigArrays.toString(a);
    }
    
    @Deprecated
    public static void ensureFromTo(final short[][] a, final long from, final long to) {
        BigArrays.ensureFromTo(length(a), from, to);
    }
    
    @Deprecated
    public static void ensureOffsetLength(final short[][] a, final long offset, final long length) {
        BigArrays.ensureOffsetLength(length(a), offset, length);
    }
    
    @Deprecated
    public static void ensureSameLength(final short[][] a, final short[][] b) {
        if (length(a) != length(b)) {
            throw new IllegalArgumentException("Array size mismatch: " + length(a) + " != " + length(b));
        }
    }
    
    private static ForkJoinPool getPool() {
        final ForkJoinPool current = ForkJoinTask.getPool();
        return (current == null) ? ForkJoinPool.commonPool() : current;
    }
    
    private static void swap(final short[][] x, long a, long b, final long n) {
        for (int i = 0; i < n; ++i, ++a, ++b) {
            BigArrays.swap(x, a, b);
        }
    }
    
    private static long med3(final short[][] x, final long a, final long b, final long c, final ShortComparator comp) {
        final int ab = comp.compare(BigArrays.get(x, a), BigArrays.get(x, b));
        final int ac = comp.compare(BigArrays.get(x, a), BigArrays.get(x, c));
        final int bc = comp.compare(BigArrays.get(x, b), BigArrays.get(x, c));
        return (ab < 0) ? ((bc < 0) ? b : ((ac < 0) ? c : a)) : ((bc > 0) ? b : ((ac > 0) ? c : a));
    }
    
    private static void selectionSort(final short[][] a, final long from, final long to, final ShortComparator comp) {
        for (long i = from; i < to - 1L; ++i) {
            long m = i;
            for (long j = i + 1L; j < to; ++j) {
                if (comp.compare(BigArrays.get(a, j), BigArrays.get(a, m)) < 0) {
                    m = j;
                }
            }
            if (m != i) {
                BigArrays.swap(a, i, m);
            }
        }
    }
    
    public static void quickSort(final short[][] x, final long from, final long to, final ShortComparator comp) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort(x, from, to, comp);
            return;
        }
        long m = from + len / 2L;
        if (len > 7L) {
            long l = from;
            long n = to - 1L;
            if (len > 40L) {
                final long s = len / 8L;
                l = med3(x, l, l + s, l + 2L * s, comp);
                m = med3(x, m - s, m, m + s, comp);
                n = med3(x, n - 2L * s, n - s, n, comp);
            }
            m = med3(x, l, m, n, comp);
        }
        final short v = BigArrays.get(x, m);
        long b;
        long a = b = from;
        long d;
        long c = d = to - 1L;
        while (true) {
            int comparison;
            if (b <= c && (comparison = comp.compare(BigArrays.get(x, b), v)) <= 0) {
                if (comparison == 0) {
                    BigArrays.swap(x, a++, b);
                }
                ++b;
            }
            else {
                while (c >= b && (comparison = comp.compare(BigArrays.get(x, c), v)) >= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, c, d--);
                    }
                    --c;
                }
                if (b > c) {
                    break;
                }
                BigArrays.swap(x, b++, c--);
            }
        }
        final long n2 = to;
        long s2 = Math.min(a - from, b - a);
        swap(x, from, b - s2, s2);
        s2 = Math.min(d - c, n2 - d - 1L);
        swap(x, b, n2 - s2, s2);
        if ((s2 = b - a) > 1L) {
            quickSort(x, from, from + s2, comp);
        }
        if ((s2 = d - c) > 1L) {
            quickSort(x, n2 - s2, n2, comp);
        }
    }
    
    private static long med3(final short[][] x, final long a, final long b, final long c) {
        final int ab = Short.compare(BigArrays.get(x, a), BigArrays.get(x, b));
        final int ac = Short.compare(BigArrays.get(x, a), BigArrays.get(x, c));
        final int bc = Short.compare(BigArrays.get(x, b), BigArrays.get(x, c));
        return (ab < 0) ? ((bc < 0) ? b : ((ac < 0) ? c : a)) : ((bc > 0) ? b : ((ac > 0) ? c : a));
    }
    
    private static void selectionSort(final short[][] a, final long from, final long to) {
        for (long i = from; i < to - 1L; ++i) {
            long m = i;
            for (long j = i + 1L; j < to; ++j) {
                if (BigArrays.get(a, j) < BigArrays.get(a, m)) {
                    m = j;
                }
            }
            if (m != i) {
                BigArrays.swap(a, i, m);
            }
        }
    }
    
    public static void quickSort(final short[][] x, final ShortComparator comp) {
        quickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static void quickSort(final short[][] x, final long from, final long to) {
        final long len = to - from;
        if (len < 7L) {
            selectionSort(x, from, to);
            return;
        }
        long m = from + len / 2L;
        if (len > 7L) {
            long l = from;
            long n = to - 1L;
            if (len > 40L) {
                final long s = len / 8L;
                l = med3(x, l, l + s, l + 2L * s);
                m = med3(x, m - s, m, m + s);
                n = med3(x, n - 2L * s, n - s, n);
            }
            m = med3(x, l, m, n);
        }
        final short v = BigArrays.get(x, m);
        long b;
        long a = b = from;
        long d;
        long c = d = to - 1L;
        while (true) {
            int comparison;
            if (b <= c && (comparison = Short.compare(BigArrays.get(x, b), v)) <= 0) {
                if (comparison == 0) {
                    BigArrays.swap(x, a++, b);
                }
                ++b;
            }
            else {
                while (c >= b && (comparison = Short.compare(BigArrays.get(x, c), v)) >= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, c, d--);
                    }
                    --c;
                }
                if (b > c) {
                    break;
                }
                BigArrays.swap(x, b++, c--);
            }
        }
        final long n2 = to;
        long s2 = Math.min(a - from, b - a);
        swap(x, from, b - s2, s2);
        s2 = Math.min(d - c, n2 - d - 1L);
        swap(x, b, n2 - s2, s2);
        if ((s2 = b - a) > 1L) {
            quickSort(x, from, from + s2);
        }
        if ((s2 = d - c) > 1L) {
            quickSort(x, n2 - s2, n2);
        }
    }
    
    public static void quickSort(final short[][] x) {
        quickSort(x, 0L, BigArrays.length(x));
    }
    
    public static void parallelQuickSort(final short[][] x, final long from, final long to) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort(x, from, to);
        }
        else {
            pool.invoke((ForkJoinTask<Object>)new ForkJoinQuickSort(x, from, to));
        }
    }
    
    public static void parallelQuickSort(final short[][] x) {
        parallelQuickSort(x, 0L, BigArrays.length(x));
    }
    
    public static void parallelQuickSort(final short[][] x, final long from, final long to, final ShortComparator comp) {
        final ForkJoinPool pool = getPool();
        if (to - from < 8192L || pool.getParallelism() == 1) {
            quickSort(x, from, to, comp);
        }
        else {
            pool.invoke((ForkJoinTask<Object>)new ForkJoinQuickSortComp(x, from, to, comp));
        }
    }
    
    public static void parallelQuickSort(final short[][] x, final ShortComparator comp) {
        parallelQuickSort(x, 0L, BigArrays.length(x), comp);
    }
    
    public static long binarySearch(final short[][] a, long from, long to, final short key) {
        --to;
        while (from <= to) {
            final long mid = from + to >>> 1;
            final short midVal = BigArrays.get(a, mid);
            if (midVal < key) {
                from = mid + 1L;
            }
            else {
                if (midVal <= key) {
                    return mid;
                }
                to = mid - 1L;
            }
        }
        return -(from + 1L);
    }
    
    public static long binarySearch(final short[][] a, final short key) {
        return binarySearch(a, 0L, BigArrays.length(a), key);
    }
    
    public static long binarySearch(final short[][] a, long from, long to, final short key, final ShortComparator c) {
        --to;
        while (from <= to) {
            final long mid = from + to >>> 1;
            final short midVal = BigArrays.get(a, mid);
            final int cmp = c.compare(midVal, key);
            if (cmp < 0) {
                from = mid + 1L;
            }
            else {
                if (cmp <= 0) {
                    return mid;
                }
                to = mid - 1L;
            }
        }
        return -(from + 1L);
    }
    
    public static long binarySearch(final short[][] a, final short key, final ShortComparator c) {
        return binarySearch(a, 0L, BigArrays.length(a), key, c);
    }
    
    public static void radixSort(final short[][] a) {
        radixSort(a, 0L, BigArrays.length(a));
    }
    
    public static void radixSort(final short[][] a, final long from, final long to) {
        final int maxLevel = 1;
        final int stackSize = 256;
        final long[] offsetStack = new long[256];
        int offsetPos = 0;
        final long[] lengthStack = new long[256];
        int lengthPos = 0;
        final int[] levelStack = new int[256];
        int levelPos = 0;
        offsetStack[offsetPos++] = from;
        lengthStack[lengthPos++] = to - from;
        levelStack[levelPos++] = 0;
        final long[] count = new long[256];
        final long[] pos = new long[256];
        final byte[][] digit = ByteBigArrays.newBigArray(to - from);
        while (offsetPos > 0) {
            final long first = offsetStack[--offsetPos];
            final long length = lengthStack[--lengthPos];
            final int level = levelStack[--levelPos];
            final int signMask = (level % 2 == 0) ? 128 : 0;
            if (length < 40L) {
                selectionSort(a, first, first + length);
            }
            else {
                final int shift = (1 - level % 2) * 8;
                long i = length;
                while (i-- != 0L) {
                    BigArrays.set(digit, i, (byte)((BigArrays.get(a, first + i) >>> shift & 0xFF) ^ signMask));
                }
                i = length;
                while (i-- != 0L) {
                    final long[] array = count;
                    final int n = BigArrays.get(digit, i) & 0xFF;
                    ++array[n];
                }
                int lastUsed = -1;
                long p = 0L;
                for (int j = 0; j < 256; ++j) {
                    if (count[j] != 0L) {
                        lastUsed = j;
                        if (level < 1 && count[j] > 1L) {
                            offsetStack[offsetPos++] = p + first;
                            lengthStack[lengthPos++] = count[j];
                            levelStack[levelPos++] = level + 1;
                        }
                    }
                    p = (pos[j] = p + count[j]);
                }
                final long end = length - count[lastUsed];
                count[lastUsed] = 0L;
                int c = -1;
                for (long k = 0L; k < end; k += count[c], count[c] = 0L) {
                    short t = BigArrays.get(a, k + first);
                    c = (BigArrays.get(digit, k) & 0xFF);
                    while (true) {
                        final long[] array2 = pos;
                        final int n2 = c;
                        final long n3 = array2[n2] - 1L;
                        array2[n2] = n3;
                        final long d = n3;
                        if (n3 <= k) {
                            break;
                        }
                        final short z = t;
                        final int zz = c;
                        t = BigArrays.get(a, d + first);
                        c = (BigArrays.get(digit, d) & 0xFF);
                        BigArrays.set(a, d + first, z);
                        BigArrays.set(digit, d, (byte)zz);
                    }
                    BigArrays.set(a, k + first, t);
                }
            }
        }
    }
    
    private static void selectionSort(final short[][] a, final short[][] b, final long from, final long to) {
        for (long i = from; i < to - 1L; ++i) {
            long m = i;
            for (long j = i + 1L; j < to; ++j) {
                if (BigArrays.get(a, j) < BigArrays.get(a, m) || (BigArrays.get(a, j) == BigArrays.get(a, m) && BigArrays.get(b, j) < BigArrays.get(b, m))) {
                    m = j;
                }
            }
            if (m != i) {
                short t = BigArrays.get(a, i);
                BigArrays.set(a, i, BigArrays.get(a, m));
                BigArrays.set(a, m, t);
                t = BigArrays.get(b, i);
                BigArrays.set(b, i, BigArrays.get(b, m));
                BigArrays.set(b, m, t);
            }
        }
    }
    
    public static void radixSort(final short[][] a, final short[][] b) {
        radixSort(a, b, 0L, BigArrays.length(a));
    }
    
    public static void radixSort(final short[][] a, final short[][] b, final long from, final long to) {
        final int layers = 2;
        if (BigArrays.length(a) != BigArrays.length(b)) {
            throw new IllegalArgumentException("Array size mismatch.");
        }
        final int maxLevel = 3;
        final int stackSize = 766;
        final long[] offsetStack = new long[766];
        int offsetPos = 0;
        final long[] lengthStack = new long[766];
        int lengthPos = 0;
        final int[] levelStack = new int[766];
        int levelPos = 0;
        offsetStack[offsetPos++] = from;
        lengthStack[lengthPos++] = to - from;
        levelStack[levelPos++] = 0;
        final long[] count = new long[256];
        final long[] pos = new long[256];
        final byte[][] digit = ByteBigArrays.newBigArray(to - from);
        while (offsetPos > 0) {
            final long first = offsetStack[--offsetPos];
            final long length = lengthStack[--lengthPos];
            final int level = levelStack[--levelPos];
            final int signMask = (level % 2 == 0) ? 128 : 0;
            if (length < 40L) {
                selectionSort(a, b, first, first + length);
            }
            else {
                final short[][] k = (level < 2) ? a : b;
                final int shift = (1 - level % 2) * 8;
                long i = length;
                while (i-- != 0L) {
                    BigArrays.set(digit, i, (byte)((BigArrays.get(k, first + i) >>> shift & 0xFF) ^ signMask));
                }
                i = length;
                while (i-- != 0L) {
                    final long[] array = count;
                    final int n = BigArrays.get(digit, i) & 0xFF;
                    ++array[n];
                }
                int lastUsed = -1;
                long p = 0L;
                for (int j = 0; j < 256; ++j) {
                    if (count[j] != 0L) {
                        lastUsed = j;
                        if (level < 3 && count[j] > 1L) {
                            offsetStack[offsetPos++] = p + first;
                            lengthStack[lengthPos++] = count[j];
                            levelStack[levelPos++] = level + 1;
                        }
                    }
                    p = (pos[j] = p + count[j]);
                }
                final long end = length - count[lastUsed];
                count[lastUsed] = 0L;
                int c = -1;
                for (long l = 0L; l < end; l += count[c], count[c] = 0L) {
                    short t = BigArrays.get(a, l + first);
                    short u = BigArrays.get(b, l + first);
                    c = (BigArrays.get(digit, l) & 0xFF);
                    while (true) {
                        final long[] array2 = pos;
                        final int n2 = c;
                        final long n3 = array2[n2] - 1L;
                        array2[n2] = n3;
                        final long d = n3;
                        if (n3 <= l) {
                            break;
                        }
                        short z = t;
                        final int zz = c;
                        t = BigArrays.get(a, d + first);
                        BigArrays.set(a, d + first, z);
                        z = u;
                        u = BigArrays.get(b, d + first);
                        BigArrays.set(b, d + first, z);
                        c = (BigArrays.get(digit, d) & 0xFF);
                        BigArrays.set(digit, d, (byte)zz);
                    }
                    BigArrays.set(a, l + first, t);
                    BigArrays.set(b, l + first, u);
                }
            }
        }
    }
    
    private static void insertionSortIndirect(final long[][] perm, final short[][] a, final short[][] b, final long from, final long to) {
        long i = from;
        while (++i < to) {
            final long t = BigArrays.get(perm, i);
            long j = i;
            for (long u = BigArrays.get(perm, j - 1L); BigArrays.get(a, t) < BigArrays.get(a, u) || (BigArrays.get(a, t) == BigArrays.get(a, u) && BigArrays.get(b, t) < BigArrays.get(b, u)); u = BigArrays.get(perm, --j - 1L)) {
                BigArrays.set(perm, j, u);
                if (from == j - 1L) {
                    --j;
                    break;
                }
            }
            BigArrays.set(perm, j, t);
        }
    }
    
    public static void radixSortIndirect(final long[][] perm, final short[][] a, final short[][] b, final boolean stable) {
        ensureSameLength(a, b);
        radixSortIndirect(perm, a, b, 0L, BigArrays.length(a), stable);
    }
    
    public static void radixSortIndirect(final long[][] perm, final short[][] a, final short[][] b, final long from, final long to, final boolean stable) {
        if (to - from < 1024L) {
            insertionSortIndirect(perm, a, b, from, to);
            return;
        }
        final int layers = 2;
        final int maxLevel = 3;
        final int stackSize = 766;
        int stackPos = 0;
        final long[] offsetStack = new long[766];
        final long[] lengthStack = new long[766];
        final int[] levelStack = new int[766];
        lengthStack[stackPos] = to - (offsetStack[stackPos] = from);
        levelStack[stackPos++] = 0;
        final long[] count = new long[256];
        final long[] pos = new long[256];
        final long[][] support = (long[][])(stable ? LongBigArrays.newBigArray(BigArrays.length(perm)) : null);
        while (stackPos > 0) {
            final long first = offsetStack[--stackPos];
            final long length = lengthStack[stackPos];
            final int level = levelStack[stackPos];
            final int signMask = (level % 2 == 0) ? 128 : 0;
            final short[][] k = (level < 2) ? a : b;
            final int shift = (1 - level % 2) * 8;
            long i = first + length;
            while (i-- != first) {
                final long[] array = count;
                final int n = (BigArrays.get(k, BigArrays.get(perm, i)) >>> shift & 0xFF) ^ signMask;
                ++array[n];
            }
            int lastUsed = -1;
            long p = stable ? 0L : first;
            for (int j = 0; j < 256; ++j) {
                if (count[j] != 0L) {
                    lastUsed = j;
                }
                p = (pos[j] = p + count[j]);
            }
            if (stable) {
                long l = first + length;
                while (l-- != first) {
                    final long[][] array2 = support;
                    final long[] array3 = pos;
                    final int n2 = (BigArrays.get(k, BigArrays.get(perm, l)) >>> shift & 0xFF) ^ signMask;
                    BigArrays.set(array2, --array3[n2], BigArrays.get(perm, l));
                }
                BigArrays.copy(support, 0L, perm, first, length);
                p = first;
                for (int j = 0; j < 256; ++j) {
                    if (level < 3 && count[j] > 1L) {
                        if (count[j] < 1024L) {
                            insertionSortIndirect(perm, a, b, p, p + count[j]);
                        }
                        else {
                            offsetStack[stackPos] = p;
                            lengthStack[stackPos] = count[j];
                            levelStack[stackPos++] = level + 1;
                        }
                    }
                    p += count[j];
                }
                Arrays.fill(count, 0L);
            }
            else {
                final long end = first + length - count[lastUsed];
                int c = -1;
                for (long m = first; m <= end; m += count[c], count[c] = 0L) {
                    long t = BigArrays.get(perm, m);
                    c = ((BigArrays.get(k, t) >>> shift & 0xFF) ^ signMask);
                    if (m < end) {
                        while (true) {
                            final long[] array4 = pos;
                            final int n3 = c;
                            final long n4 = array4[n3] - 1L;
                            array4[n3] = n4;
                            final long d = n4;
                            if (n4 <= m) {
                                break;
                            }
                            final long z = t;
                            t = BigArrays.get(perm, d);
                            BigArrays.set(perm, d, z);
                            c = ((BigArrays.get(k, t) >>> shift & 0xFF) ^ signMask);
                        }
                        BigArrays.set(perm, m, t);
                    }
                    if (level < 3 && count[c] > 1L) {
                        if (count[c] < 1024L) {
                            insertionSortIndirect(perm, a, b, m, m + count[c]);
                        }
                        else {
                            offsetStack[stackPos] = m;
                            lengthStack[stackPos] = count[c];
                            levelStack[stackPos++] = level + 1;
                        }
                    }
                }
            }
        }
    }
    
    public static short[][] shuffle(final short[][] a, final long from, final long to, final Random random) {
        return BigArrays.shuffle(a, from, to, random);
    }
    
    public static short[][] shuffle(final short[][] a, final Random random) {
        return BigArrays.shuffle(a, random);
    }
    
    static {
        EMPTY_BIG_ARRAY = new short[0][];
        DEFAULT_EMPTY_BIG_ARRAY = new short[0][];
        HASH_STRATEGY = new BigArrayHashStrategy();
    }
    
    private static final class BigArrayHashStrategy implements Hash.Strategy<short[][]>, Serializable
    {
        private static final long serialVersionUID = -7046029254386353129L;
        
        @Override
        public int hashCode(final short[][] o) {
            return Arrays.deepHashCode(o);
        }
        
        @Override
        public boolean equals(final short[][] a, final short[][] b) {
            return ShortBigArrays.equals(a, b);
        }
    }
    
    protected static class ForkJoinQuickSort extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final short[][] x;
        
        public ForkJoinQuickSort(final short[][] x, final long from, final long to) {
            this.from = from;
            this.to = to;
            this.x = x;
        }
        
        @Override
        protected void compute() {
            final short[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                ShortBigArrays.quickSort(x, this.from, this.to);
                return;
            }
            long m = this.from + len / 2L;
            long l = this.from;
            long n = this.to - 1L;
            long s = len / 8L;
            l = med3(x, l, l + s, l + 2L * s);
            m = med3(x, m - s, m, m + s);
            n = med3(x, n - 2L * s, n - s, n);
            m = med3(x, l, m, n);
            final short v = BigArrays.get(x, m);
            long b;
            long a = b = this.from;
            long d;
            long c = d = this.to - 1L;
            while (true) {
                int comparison;
                if (b <= c && (comparison = Short.compare(BigArrays.get(x, b), v)) <= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, a++, b);
                    }
                    ++b;
                }
                else {
                    while (c >= b && (comparison = Short.compare(BigArrays.get(x, c), v)) >= 0) {
                        if (comparison == 0) {
                            BigArrays.swap(x, c, d--);
                        }
                        --c;
                    }
                    if (b > c) {
                        break;
                    }
                    BigArrays.swap(x, b++, c--);
                }
            }
            s = Math.min(a - this.from, b - a);
            swap(x, this.from, b - s, s);
            s = Math.min(d - c, this.to - d - 1L);
            swap(x, b, this.to - s, s);
            s = b - a;
            final long t = d - c;
            if (s > 1L && t > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort(x, this.from, this.from + s), new ForkJoinQuickSort(x, this.to - t, this.to));
            }
            else if (s > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort(x, this.from, this.from + s));
            }
            else {
                ForkJoinTask.invokeAll(new ForkJoinQuickSort(x, this.to - t, this.to));
            }
        }
    }
    
    protected static class ForkJoinQuickSortComp extends RecursiveAction
    {
        private static final long serialVersionUID = 1L;
        private final long from;
        private final long to;
        private final short[][] x;
        private final ShortComparator comp;
        
        public ForkJoinQuickSortComp(final short[][] x, final long from, final long to, final ShortComparator comp) {
            this.from = from;
            this.to = to;
            this.x = x;
            this.comp = comp;
        }
        
        @Override
        protected void compute() {
            final short[][] x = this.x;
            final long len = this.to - this.from;
            if (len < 8192L) {
                ShortBigArrays.quickSort(x, this.from, this.to, this.comp);
                return;
            }
            long m = this.from + len / 2L;
            long l = this.from;
            long n = this.to - 1L;
            long s = len / 8L;
            l = med3(x, l, l + s, l + 2L * s, this.comp);
            m = med3(x, m - s, m, m + s, this.comp);
            n = med3(x, n - 2L * s, n - s, n, this.comp);
            m = med3(x, l, m, n, this.comp);
            final short v = BigArrays.get(x, m);
            long b;
            long a = b = this.from;
            long d;
            long c = d = this.to - 1L;
            while (true) {
                int comparison;
                if (b <= c && (comparison = this.comp.compare(BigArrays.get(x, b), v)) <= 0) {
                    if (comparison == 0) {
                        BigArrays.swap(x, a++, b);
                    }
                    ++b;
                }
                else {
                    while (c >= b && (comparison = this.comp.compare(BigArrays.get(x, c), v)) >= 0) {
                        if (comparison == 0) {
                            BigArrays.swap(x, c, d--);
                        }
                        --c;
                    }
                    if (b > c) {
                        break;
                    }
                    BigArrays.swap(x, b++, c--);
                }
            }
            s = Math.min(a - this.from, b - a);
            swap(x, this.from, b - s, s);
            s = Math.min(d - c, this.to - d - 1L);
            swap(x, b, this.to - s, s);
            s = b - a;
            final long t = d - c;
            if (s > 1L && t > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp(x, this.from, this.from + s, this.comp), new ForkJoinQuickSortComp(x, this.to - t, this.to, this.comp));
            }
            else if (s > 1L) {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp(x, this.from, this.from + s, this.comp));
            }
            else {
                ForkJoinTask.invokeAll(new ForkJoinQuickSortComp(x, this.to - t, this.to, this.comp));
            }
        }
    }
}