Sorting.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.numbers.arrays;

import java.util.Arrays;

/**
 * Support class for sorting arrays.
 *
 * <p>Optimal sorting networks are used for small fixed size array sorting.
 *
 * <p>Note: Requires that the floating-point data contains no NaN values; sorting
 * does not respect the order of signed zeros imposed by {@link Double#compare(double, double)}.
 *
 * @see <a href="https://en.wikipedia.org/wiki/Sorting_network">Sorting network (Wikipedia)</a>
 * @see <a href="https://bertdobbelaere.github.io/sorting_networks.html">Sorting Networks (Bert Dobbelaere)</a>
 *
 * @since 1.2
 */
final class Sorting {

    /** No instances. */
    private Sorting() {}

    /**
     * Sorts an array using an insertion sort.
     *
     * @param x Data array.
     * @param left Lower bound (inclusive).
     * @param right Upper bound (inclusive).
     */
    static void sort(double[] x, int left, int right) {
        for (int i = left; ++i <= right;) {
            final double v = x[i];
            // Move preceding higher elements above (if required)
            if (v < x[i - 1]) {
                int j = i;
                while (--j >= left && v < x[j]) {
                    x[j + 1] = x[j];
                }
                x[j + 1] = v;
            }
        }
    }

    /**
     * Sorts the elements at the given distinct indices in an array.
     *
     * @param x Data array.
     * @param a Index.
     * @param b Index.
     * @param c Index.
     */
    static void sort3(double[] x, int a, int b, int c) {
        // Decision tree avoiding swaps:
        // Order [(0,2)]
        // Move point 1 above point 2 or below point 0
        final double u = x[a];
        final double v = x[b];
        final double w = x[c];
        if (w < u) {
            if (v < w) {
                x[a] = v;
                x[b] = w;
                x[c] = u;
                return;
            }
            if (u < v) {
                x[a] = w;
                x[b] = u;
                x[c] = v;
                return;
            }
            // w < v < u
            x[a] = w;
            x[c] = u;
            return;
        }
        if (v < u) {
            // v < u < w
            x[a] = v;
            x[b] = u;
            return;
        }
        if (w < v) {
            // u < w < v
            x[b] = w;
            x[c] = v;
        }
        // u < v < w
    }

    /**
     * Sorts the elements at the given distinct indices in an array.
     *
     * @param x Data array.
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     * @param e Index.
     */
    static void sort5(double[] x, int a, int b, int c, int d, int e) {
        // Uses an optimal sorting network from Knuth's Art of Computer Programming.
        // 9 comparisons.
        // Order pairs:
        // [(0,3),(1,4)]
        // [(0,2),(1,3)]
        // [(0,1),(2,4)]
        // [(1,2),(3,4)]
        // [(2,3)]
        if (x[e] < x[b]) {
            final double u = x[e];
            x[e] = x[b];
            x[b] = u;
        }
        if (x[d] < x[a]) {
            final double v = x[d];
            x[d] = x[a];
            x[a] = v;
        }

        if (x[d] < x[b]) {
            final double u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final double v = x[c];
            x[c] = x[a];
            x[a] = v;
        }

        if (x[e] < x[c]) {
            final double u = x[e];
            x[e] = x[c];
            x[c] = u;
        }
        if (x[b] < x[a]) {
            final double v = x[b];
            x[b] = x[a];
            x[a] = v;
        }

        if (x[e] < x[d]) {
            final double u = x[e];
            x[e] = x[d];
            x[d] = u;
        }
        if (x[c] < x[b]) {
            final double v = x[c];
            x[c] = x[b];
            x[b] = v;
        }

        if (x[d] < x[c]) {
            final double u = x[d];
            x[d] = x[c];
            x[c] = u;
        }
    }

    /**
     * Place the lower median of 4 elements in {@code b}; the smaller element in
     * {@code a}; and the larger two elements in {@code c, d}.
     *
     * @param x Values
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     */
    static void lowerMedian4(double[] x, int a, int b, int c, int d) {
        // 3 to 5 comparisons
        if (x[d] < x[b]) {
            final double u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final double v = x[c];
            x[c] = x[a];
            x[a] = v;
        }
        // a--c
        // b--d
        if (x[c] < x[b]) {
            final double u = x[c];
            x[c] = x[b];
            x[b] = u;
        } else if (x[b] < x[a]) {
            //    a--c
            // b--d
            final double xb = x[a];
            x[a] = x[b];
            x[b] = xb;
            //    b--c
            // a--d
            if (x[d] < xb) {
                x[b] = x[d];
                // Move a pair to maintain the sorted order
                x[d] = x[c];
                x[c] = xb;
            }
        }
    }

    /**
     * Place the upper median of 4 elements in {@code c}; the smaller two elements in
     * {@code a,b}; and the larger element in {@code d}.
     *
     * @param x Values
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     */
    static void upperMedian4(double[] x, int a, int b, int c, int d) {
        // 3 to 5 comparisons
        if (x[d] < x[b]) {
            final double u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final double v = x[c];
            x[c] = x[a];
            x[a] = v;
        }
        // a--c
        // b--d
        if (x[b] > x[c]) {
            final double u = x[c];
            x[c] = x[b];
            x[b] = u;
        } else if (x[c] > x[d]) {
            //    a--c
            // b--d
            final double xc = x[d];
            x[d] = x[c];
            x[c] = xc;
            //    a--d
            // b--c
            if (x[a] > xc) {
                x[c] = x[a];
                // Move a pair to maintain the sorted order
                x[a] = x[b];
                x[b] = xc;
            }
        }
    }

    /**
     * Sorts an array using an insertion sort.
     *
     * @param x Data array.
     * @param left Lower bound (inclusive).
     * @param right Upper bound (inclusive).
     */
    static void sort(int[] x, int left, int right) {
        for (int i = left; ++i <= right;) {
            final int v = x[i];
            // Move preceding higher elements above (if required)
            if (v < x[i - 1]) {
                int j = i;
                while (--j >= left && v < x[j]) {
                    x[j + 1] = x[j];
                }
                x[j + 1] = v;
            }
        }
    }

    /**
     * Sorts the elements at the given distinct indices in an array.
     *
     * @param x Data array.
     * @param a Index.
     * @param b Index.
     * @param c Index.
     */
    static void sort3(int[] x, int a, int b, int c) {
        // Decision tree avoiding swaps:
        // Order [(0,2)]
        // Move point 1 above point 2 or below point 0
        final int u = x[a];
        final int v = x[b];
        final int w = x[c];
        if (w < u) {
            if (v < w) {
                x[a] = v;
                x[b] = w;
                x[c] = u;
                return;
            }
            if (u < v) {
                x[a] = w;
                x[b] = u;
                x[c] = v;
                return;
            }
            // w < v < u
            x[a] = w;
            x[c] = u;
            return;
        }
        if (v < u) {
            // v < u < w
            x[a] = v;
            x[b] = u;
            return;
        }
        if (w < v) {
            // u < w < v
            x[b] = w;
            x[c] = v;
        }
        // u < v < w
    }

    /**
     * Sorts the elements at the given distinct indices in an array.
     *
     * @param x Data array.
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     * @param e Index.
     */
    static void sort5(int[] x, int a, int b, int c, int d, int e) {
        // Uses an optimal sorting network from Knuth's Art of Computer Programming.
        // 9 comparisons.
        // Order pairs:
        // [(0,3),(1,4)]
        // [(0,2),(1,3)]
        // [(0,1),(2,4)]
        // [(1,2),(3,4)]
        // [(2,3)]
        if (x[e] < x[b]) {
            final int u = x[e];
            x[e] = x[b];
            x[b] = u;
        }
        if (x[d] < x[a]) {
            final int v = x[d];
            x[d] = x[a];
            x[a] = v;
        }

        if (x[d] < x[b]) {
            final int u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final int v = x[c];
            x[c] = x[a];
            x[a] = v;
        }

        if (x[e] < x[c]) {
            final int u = x[e];
            x[e] = x[c];
            x[c] = u;
        }
        if (x[b] < x[a]) {
            final int v = x[b];
            x[b] = x[a];
            x[a] = v;
        }

        if (x[e] < x[d]) {
            final int u = x[e];
            x[e] = x[d];
            x[d] = u;
        }
        if (x[c] < x[b]) {
            final int v = x[c];
            x[c] = x[b];
            x[b] = v;
        }

        if (x[d] < x[c]) {
            final int u = x[d];
            x[d] = x[c];
            x[c] = u;
        }
    }

    /**
     * Place the lower median of 4 elements in {@code b}; the smaller element in
     * {@code a}; and the larger two elements in {@code c, d}.
     *
     * @param x Values
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     */
    static void lowerMedian4(int[] x, int a, int b, int c, int d) {
        // 3 to 5 comparisons
        if (x[d] < x[b]) {
            final int u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final int v = x[c];
            x[c] = x[a];
            x[a] = v;
        }
        // a--c
        // b--d
        if (x[c] < x[b]) {
            final int u = x[c];
            x[c] = x[b];
            x[b] = u;
        } else if (x[b] < x[a]) {
            //    a--c
            // b--d
            final int xb = x[a];
            x[a] = x[b];
            x[b] = xb;
            //    b--c
            // a--d
            if (x[d] < xb) {
                x[b] = x[d];
                // Move a pair to maintain the sorted order
                x[d] = x[c];
                x[c] = xb;
            }
        }
    }

    /**
     * Place the upper median of 4 elements in {@code c}; the smaller two elements in
     * {@code a,b}; and the larger element in {@code d}.
     *
     * @param x Values
     * @param a Index.
     * @param b Index.
     * @param c Index.
     * @param d Index.
     */
    static void upperMedian4(int[] x, int a, int b, int c, int d) {
        // 3 to 5 comparisons
        if (x[d] < x[b]) {
            final int u = x[d];
            x[d] = x[b];
            x[b] = u;
        }
        if (x[c] < x[a]) {
            final int v = x[c];
            x[c] = x[a];
            x[a] = v;
        }
        // a--c
        // b--d
        if (x[b] > x[c]) {
            final int u = x[c];
            x[c] = x[b];
            x[b] = u;
        } else if (x[c] > x[d]) {
            //    a--c
            // b--d
            final int xc = x[d];
            x[d] = x[c];
            x[c] = xc;
            //    a--d
            // b--c
            if (x[a] > xc) {
                x[c] = x[a];
                // Move a pair to maintain the sorted order
                x[a] = x[b];
                x[b] = xc;
            }
        }
    }

    /**
     * Sort the unique indices in-place to the start of the array. The number of
     * unique indices is returned.
     *
     * <p>Uses an insertion sort modified to ignore duplicates. Use on small {@code n}.
     *
     * <p>Warning: Requires {@code n > 0}. The array contents after the count of unique
     * indices {@code c} are unchanged (i.e. {@code [c, n)}. This may change the count of
     * each unique index in the entire array.
     *
     * @param x Indices.
     * @param n Number of indices.
     * @return the number of unique indices
     */
    static int insertionSortIndices(int[] x, int n) {
        // Index of last unique value
        int unique = 0;
        // Do an insertion sort but only compare the current set of unique values.
        for (int i = 0; ++i < n;) {
            final int v = x[i];
            int j = unique;
            if (v > x[j]) {
                // Insert at end
                x[++unique] = v;
            } else if (v < x[j]) {
                // Find insertion point in the unique indices
                do {
                    --j;
                } while (j >= 0 && v < x[j]);
                // Insertion point = j + 1
                // Insert if at start or non-duplicate
                if (j < 0 || v != x[j]) {
                    // Move (j, unique] to (j+1, unique+1]
                    for (int k = unique; k > j; --k) {
                        x[k + 1] = x[k];
                    }
                    x[j + 1] = v;
                    ++unique;
                }
            }
        }
        return unique + 1;
    }

    /**
     * Sort the unique indices in-place to the start of the array. The number of
     * unique indices is returned.
     *
     * <p>Uses an Order(1) data structure to ignore duplicates.
     *
     * <p>Warning: Requires {@code n > 0}. The array contents after the count of unique
     * indices {@code c} are unchanged (i.e. {@code [c, n)}. This may change the count of
     * each unique index in the entire array.
     *
     * @param x Indices.
     * @param n Number of indices.
     * @return the number of unique indices
     */
    static int sortIndices(int[] x, int n) {
        // Duplicates are checked using a primitive hash set.
        // Storage (bytes) = 4 * next-power-of-2(n*2) => 2-4 times n
        final HashIndexSet set = HashIndexSet.create(n);
        int i = 0;
        int last = 0;
        set.add(x[0]);
        while (++i < n) {
            final int v = x[i];
            if (set.add(v)) {
                x[++last] = v;
            }
        }
        Arrays.sort(x, 0, ++last);
        return last;
    }
}