Class Sorting


  • final class Sorting
    extends java.lang.Object
    Support class for sorting arrays.

    Optimal sorting networks are used for small fixed size array sorting.

    Note: Requires that the floating-point data contains no NaN values; sorting does not respect the order of signed zeros imposed by Double.compare(double, double).

    Since:
    1.2
    See Also:
    Sorting network (Wikipedia), Sorting Networks (Bert Dobbelaere)
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private Sorting()
      No instances.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static int insertionSortIndices​(int[] x, int n)
      Sort the unique indices in-place to the start of the array.
      (package private) static void lowerMedian4​(double[] x, int a, int b, int c, int d)
      Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
      (package private) static void lowerMedian4​(int[] x, int a, int b, int c, int d)
      Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
      (package private) static void sort​(double[] x, int left, int right)
      Sorts an array using an insertion sort.
      (package private) static void sort​(int[] x, int left, int right)
      Sorts an array using an insertion sort.
      (package private) static void sort3​(double[] x, int a, int b, int c)
      Sorts the elements at the given distinct indices in an array.
      (package private) static void sort3​(int[] x, int a, int b, int c)
      Sorts the elements at the given distinct indices in an array.
      (package private) static void sort5​(double[] x, int a, int b, int c, int d, int e)
      Sorts the elements at the given distinct indices in an array.
      (package private) static void sort5​(int[] x, int a, int b, int c, int d, int e)
      Sorts the elements at the given distinct indices in an array.
      (package private) static int sortIndices​(int[] x, int n)
      Sort the unique indices in-place to the start of the array.
      (package private) static void upperMedian4​(double[] x, int a, int b, int c, int d)
      Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
      (package private) static void upperMedian4​(int[] x, int a, int b, int c, int d)
      Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Sorting

        private Sorting()
        No instances.
    • Method Detail

      • sort

        static void sort​(double[] x,
                         int left,
                         int right)
        Sorts an array using an insertion sort.
        Parameters:
        x - Data array.
        left - Lower bound (inclusive).
        right - Upper bound (inclusive).
      • sort3

        static void sort3​(double[] x,
                          int a,
                          int b,
                          int c)
        Sorts the elements at the given distinct indices in an array.
        Parameters:
        x - Data array.
        a - Index.
        b - Index.
        c - Index.
      • sort5

        static void sort5​(double[] x,
                          int a,
                          int b,
                          int c,
                          int d,
                          int e)
        Sorts the elements at the given distinct indices in an array.
        Parameters:
        x - Data array.
        a - Index.
        b - Index.
        c - Index.
        d - Index.
        e - Index.
      • lowerMedian4

        static void lowerMedian4​(double[] x,
                                 int a,
                                 int b,
                                 int c,
                                 int d)
        Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
        Parameters:
        x - Values
        a - Index.
        b - Index.
        c - Index.
        d - Index.
      • upperMedian4

        static void upperMedian4​(double[] x,
                                 int a,
                                 int b,
                                 int c,
                                 int d)
        Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
        Parameters:
        x - Values
        a - Index.
        b - Index.
        c - Index.
        d - Index.
      • sort

        static void sort​(int[] x,
                         int left,
                         int right)
        Sorts an array using an insertion sort.
        Parameters:
        x - Data array.
        left - Lower bound (inclusive).
        right - Upper bound (inclusive).
      • sort3

        static void sort3​(int[] x,
                          int a,
                          int b,
                          int c)
        Sorts the elements at the given distinct indices in an array.
        Parameters:
        x - Data array.
        a - Index.
        b - Index.
        c - Index.
      • sort5

        static void sort5​(int[] x,
                          int a,
                          int b,
                          int c,
                          int d,
                          int e)
        Sorts the elements at the given distinct indices in an array.
        Parameters:
        x - Data array.
        a - Index.
        b - Index.
        c - Index.
        d - Index.
        e - Index.
      • lowerMedian4

        static void lowerMedian4​(int[] x,
                                 int a,
                                 int b,
                                 int c,
                                 int d)
        Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
        Parameters:
        x - Values
        a - Index.
        b - Index.
        c - Index.
        d - Index.
      • upperMedian4

        static void upperMedian4​(int[] x,
                                 int a,
                                 int b,
                                 int c,
                                 int d)
        Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
        Parameters:
        x - Values
        a - Index.
        b - Index.
        c - Index.
        d - Index.
      • insertionSortIndices

        static int insertionSortIndices​(int[] x,
                                        int n)
        Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

        Uses an insertion sort modified to ignore duplicates. Use on small n.

        Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

        Parameters:
        x - Indices.
        n - Number of indices.
        Returns:
        the number of unique indices
      • sortIndices

        static int sortIndices​(int[] x,
                               int n)
        Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

        Uses an Order(1) data structure to ignore duplicates.

        Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

        Parameters:
        x - Indices.
        n - Number of indices.
        Returns:
        the number of unique indices