sort 40M float pairs lexicographically

import java.util.Random;

/*

Generation time: 1028 msec
Sort time: 10854 msec

*/


public class Sort40M {

    public static void sort(int fromIndex, int toIndex) {
        sort2(fromIndex, toIndex);
    }

    static float compare(int ix1, int ix2) {
        float v1 = a[ix1*2];
        float v2 = a[ix2*2];
        if (v1 == v2) {
            return a[ix1*2+1] - a[ix2*2+1];
        } else {
            return a[ix1*2] - a[ix2*2];
        }
    }

    static float compare2(int ix1, float v2a, float v2b) {
        float v1 = a[ix1*2];
        if (v1 == v2a) {
            return a[ix1*2+1] - v2b;
        } else {
            return a[ix1*2] - v2a;
        }
    }

    private static void sort2(int fromIndex, int toIndex) {
        final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
        /*
         * The sort is done in three phases to avoid the expense of using
         * NaN and -0.0 aware comparisons during the main sort.
         */

        /*
         * Preprocessing phase:  Move any NaN's to end of array, count the
         * number of -0.0's, and turn them into 0.0's.
         */
        int numNegZeros = 0;
        int i = fromIndex, n = toIndex;

        // Main sort phase: quicksort everything but the NaN's
        sort1(fromIndex, n - fromIndex);

    }

    // Like public version, but without range checks.
    private static int binarySearch0(int fromIndex, int toIndex,
                                     float key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            float midVal = a[mid];

            int cmp;
            if (midVal < key) {
                cmp = -1;   // Neither val is NaN, thisVal is smaller
            } else if (midVal > key) {
                cmp = 1;    // Neither val is NaN, thisVal is larger
            } else {
                int midBits = Float.floatToIntBits(midVal);
                int keyBits = Float.floatToIntBits(key);
                cmp = (midBits == keyBits ? 0 : // Values are equal
                        (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                                1));                     // (0.0, -0.0) or (NaN, !NaN)
            }

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

    /**
     * Sorts the specified sub-array of floats into ascending order.
     */
    private static void sort1(int off, int len) {
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i = off; i < len + off; i++)
                for (int j = i; j > off && a[j - 1] > a[j]; j--)
                    swap(j, j - 1);
            return;
        }

        // Choose a partition element, v
        int m = off + (len >> 1);       // Small arrays, middle element
        if (len > 7) {
            int l = off;
            int n = off + len - 1;
            if (len > 40) {        // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = med3(a, l, l + s, l + 2 * s);
                m = med3(a, m - s, m, m + s);
                n = med3(a, n - 2 * s, n - s, n);
            }
            m = med3(a, l, m, n); // Mid-size, med of 3
        }
        float v = a[m*2];
        float v1 = a[m*2+1];

        // Establish Invariant: v* (<v)* (>v)* v*
        int aa = off, bb = aa, cc = off + len - 1, dd = cc;
        while (true) {
            while (bb <= cc && compare2(bb, v, v1) <= 0) {
                if (compare2(bb, v, v1) == 0)
                    swap(aa++, bb);
                bb++;
            }
            while (cc >= bb && compare2(cc, v, v1) >= 0) {
                if (compare2(cc, v, v1) == 0)
                    swap(cc, dd--);
                cc--;
            }
            if (bb > cc)
                break;
            swap(bb++, cc--);
        }

        // Swap partition elements back to middle
        int s, n = off + len;
        s = Math.min(aa - off, bb - aa);
        vecswap(off, bb - s, s);
        s = Math.min(dd - cc, n - dd - 1);
        vecswap(bb, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = bb - aa) > 1)
            sort1(off, s);
        if ((s = dd - cc) > 1)
            sort1(n - s, s);
    }

    private static void swap(int aa, int bb) {
        float t = a[aa*2];
        a[aa*2] = a[bb*2];
        a[bb*2] = t;
        t = a[aa*2+1];
        a[aa*2+1] = a[bb*2+1];
        a[bb*2+1] = t;
    }

    private static void vecswap(int aa, int bb, int n) {
        for (int i = 0; i < n; i++, aa++, bb++)
            swap(aa, bb);
    }


    private static int med3(float x[], int a, int b, int c) {
        return (compare(a, b) < 0 ?
                (compare(b, c) < 0 ? b : compare(a, c) < 0 ? c : a) :
                (compare(b, c) > 0 ? b : compare(a, c) > 0 ? c : a));
    }

    public static final int M = 40000000;
    public static float a[] = new float[M * 2];

    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        Random random = new Random(0);
        final float[] d = a;
        for (int i = 0; i < M; i++) {
            d[2 * i] = random.nextFloat();
            d[2 * i + 1] = random.nextFloat();
        }
        l = System.currentTimeMillis() - l;
        System.out.println("Generation time: " + l + " msec");
        l = System.currentTimeMillis();
        sort(0, M-1);
        l = System.currentTimeMillis() - l;
        System.out.println("Sort time: " + l + " msec");
    }
}