Package cern.colt

Class Sorting


  • public class Sorting
    extends java.lang.Object
    Quicksorts, mergesorts and binary searches; complements java.util.Arrays. Contains, for example, the quicksort on Comparators and Comparables, which are still missing in java.util.Arrays of JDK 1.2. Also provides mergesorts for types not supported in java.util.Arrays, as well as a couple of other methods for primitive arrays. The quicksorts and mergesorts are the JDK 1.2 V1.26 algorithms, modified as necessary.
    Version:
    1.0, 03-Jul-99
    See Also:
    GenericSorting, Sorting, Arrays
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int MEDIUM  
      private static int SMALL  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected Sorting()
      Makes this class non instantiable, but still let's others inherit from it.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static int binarySearchFromTo​(byte[] list, byte key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(char[] list, char key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(double[] list, double key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(float[] list, float key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(int[] list, int key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(int from, int to, IntComparator comp)
      Generically searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(long[] list, long key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(short[] list, short key, int from, int to)
      Searches the list for the specified value using the binary search algorithm.
      static int binarySearchFromTo​(java.lang.Object[] list, java.lang.Object key, int from, int to, java.util.Comparator comparator)
      Searches the list for the specified value using the binary search algorithm.
      private static void inplace_merge​(int[] array, int first, int middle, int last)  
      private static int lower_bound​(int[] array, int first, int last, int x)  
      private static int med3​(byte[] x, int a, int b, int c, ByteComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(char[] x, int a, int b, int c, CharComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(double[] x, int a, int b, int c, DoubleComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(float[] x, int a, int b, int c, FloatComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(int[] x, int a, int b, int c, IntComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(long[] x, int a, int b, int c, LongComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(short[] x, int a, int b, int c, ShortComparator comp)
      Returns the index of the median of the three indexed chars.
      private static int med3​(java.lang.Object[] x, int a, int b, int c)
      Returns the index of the median of the three indexed chars.
      private static int med3​(java.lang.Object[] x, int a, int b, int c, java.util.Comparator comp)
      Returns the index of the median of the three indexed chars.
      static void mergeSort​(byte[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(byte[] a, int fromIndex, int toIndex, ByteComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(char[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(char[] a, int fromIndex, int toIndex, CharComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(double[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(double[] a, int fromIndex, int toIndex, DoubleComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(float[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(float[] a, int fromIndex, int toIndex, FloatComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(int[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(int[] a, int fromIndex, int toIndex, IntComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(long[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(long[] a, int fromIndex, int toIndex, LongComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void mergeSort​(short[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void mergeSort​(short[] a, int fromIndex, int toIndex, ShortComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      private static void mergeSort1​(byte[] src, byte[] dest, int low, int high)  
      private static void mergeSort1​(byte[] src, byte[] dest, int low, int high, ByteComparator c)  
      private static void mergeSort1​(char[] src, char[] dest, int low, int high)  
      private static void mergeSort1​(char[] src, char[] dest, int low, int high, CharComparator c)  
      private static void mergeSort1​(double[] src, double[] dest, int low, int high)  
      private static void mergeSort1​(double[] src, double[] dest, int low, int high, DoubleComparator c)  
      private static void mergeSort1​(float[] src, float[] dest, int low, int high)  
      private static void mergeSort1​(float[] src, float[] dest, int low, int high, FloatComparator c)  
      private static void mergeSort1​(int[] src, int[] dest, int low, int high)  
      private static void mergeSort1​(int[] src, int[] dest, int low, int high, IntComparator c)  
      private static void mergeSort1​(long[] src, long[] dest, int low, int high)  
      private static void mergeSort1​(long[] src, long[] dest, int low, int high, LongComparator c)  
      private static void mergeSort1​(short[] src, short[] dest, int low, int high)  
      private static void mergeSort1​(short[] src, short[] dest, int low, int high, ShortComparator c)  
      private static void mergeSort2​(double[] a, int fromIndex, int toIndex)  
      private static void mergeSort2​(float[] a, int fromIndex, int toIndex)  
      static void mergeSortInPlace​(int[] a, int fromIndex, int toIndex)
      Sorts the specified range of the specified array of elements.
      static void quickSort​(byte[] a, int fromIndex, int toIndex, ByteComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(char[] a, int fromIndex, int toIndex, CharComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(double[] a, int fromIndex, int toIndex, DoubleComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(float[] a, int fromIndex, int toIndex, FloatComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(int[] a, int fromIndex, int toIndex, IntComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(long[] a, int fromIndex, int toIndex, LongComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(short[] a, int fromIndex, int toIndex, ShortComparator c)
      Sorts the specified range of the specified array of elements according to the order induced by the specified comparator.
      static void quickSort​(java.lang.Object[] a)
      Sorts the specified range of the receiver into ascending order, according to the natural ordering of its elements.
      static void quickSort​(java.lang.Object[] a, int fromIndex, int toIndex)
      Sorts the specified range of the receiver into ascending order, according to the natural ordering of its elements.
      static void quickSort​(java.lang.Object[] a, int fromIndex, int toIndex, java.util.Comparator c)
      Sorts the specified range of the specified array according to the order induced by the specified comparator.
      static void quickSort​(java.lang.Object[] a, java.util.Comparator c)
      Sorts the specified array according to the order induced by the specified comparator.
      private static void quickSort1​(byte[] x, int off, int len, ByteComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(char[] x, int off, int len, CharComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(double[] x, int off, int len, DoubleComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(float[] x, int off, int len, FloatComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(int[] x, int off, int len, IntComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(long[] x, int off, int len, LongComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(short[] x, int off, int len, ShortComparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(java.lang.Object[] x, int off, int len)
      Sorts the specified sub-array of chars into ascending order.
      private static void quickSort1​(java.lang.Object[] x, int off, int len, java.util.Comparator comp)
      Sorts the specified sub-array of chars into ascending order.
      private static void rangeCheck​(int arrayLen, int fromIndex, int toIndex)
      Check that fromIndex and toIndex are in range, and throw an appropriate exception if they aren't.
      private static void swap​(byte[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(char[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(double[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(float[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(int[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(long[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(short[] x, int a, int b)
      Swaps x[a] with x[b].
      private static void swap​(java.lang.Object[] x, int a, int b)
      Swaps x[a] with x[b].
      private static int upper_bound​(int[] array, int first, int last, int x)  
      private static void vecswap​(byte[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(char[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(double[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(float[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(int[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(long[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(short[] x, int a, int b, int n)
      Swaps x[a ..
      private static void vecswap​(java.lang.Object[] x, int a, int b, int n)
      Swaps x[a ..
      • Methods inherited from class java.lang.Object

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

      • Sorting

        protected Sorting()
        Makes this class non instantiable, but still let's others inherit from it.
    • Method Detail

      • binarySearchFromTo

        public static int binarySearchFromTo​(byte[] list,
                                             byte key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(char[] list,
                                             char key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(double[] list,
                                             double key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(float[] list,
                                             float key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(int[] list,
                                             int key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(long[] list,
                                             long key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(java.lang.Object[] list,
                                             java.lang.Object key,
                                             int from,
                                             int to,
                                             java.util.Comparator comparator)
        Searches the list for the specified value using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        If the list is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which instance will be found.

        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        comparator - the comparator by which the list is sorted.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        Throws:
        java.lang.ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator.
        See Also:
        Arrays, Comparator
      • binarySearchFromTo

        public static int binarySearchFromTo​(short[] list,
                                             short key,
                                             int from,
                                             int to)
        Searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • binarySearchFromTo

        public static int binarySearchFromTo​(int from,
                                             int to,
                                             IntComparator comp)
        Generically searches the list for the specified value using the binary search algorithm. The list must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the list contains multiple elements equal to the specified key, there is no guarantee which of the multiple elements will be found.
        Parameters:
        list - the list to be searched.
        key - the value to be searched for.
        from - the leftmost search position, inclusive.
        to - the rightmost search position, inclusive.
        Returns:
        index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the list: the index of the first element greater than the key, or list.length, if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
        See Also:
        Arrays
      • lower_bound

        private static int lower_bound​(int[] array,
                                       int first,
                                       int last,
                                       int x)
      • upper_bound

        private static int upper_bound​(int[] array,
                                       int first,
                                       int last,
                                       int x)
      • inplace_merge

        private static void inplace_merge​(int[] array,
                                          int first,
                                          int middle,
                                          int last)
      • med3

        private static int med3​(byte[] x,
                                int a,
                                int b,
                                int c,
                                ByteComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(char[] x,
                                int a,
                                int b,
                                int c,
                                CharComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(double[] x,
                                int a,
                                int b,
                                int c,
                                DoubleComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(float[] x,
                                int a,
                                int b,
                                int c,
                                FloatComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(int[] x,
                                int a,
                                int b,
                                int c,
                                IntComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(long[] x,
                                int a,
                                int b,
                                int c,
                                LongComparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(java.lang.Object[] x,
                                int a,
                                int b,
                                int c)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(java.lang.Object[] x,
                                int a,
                                int b,
                                int c,
                                java.util.Comparator comp)
        Returns the index of the median of the three indexed chars.
      • med3

        private static int med3​(short[] x,
                                int a,
                                int b,
                                int c,
                                ShortComparator comp)
        Returns the index of the median of the three indexed chars.
      • mergeSort

        public static void mergeSort​(byte[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(byte[] a,
                                     int fromIndex,
                                     int toIndex,
                                     ByteComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(char[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(char[] a,
                                     int fromIndex,
                                     int toIndex,
                                     CharComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(double[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(double[] a,
                                     int fromIndex,
                                     int toIndex,
                                     DoubleComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(float[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(float[] a,
                                     int fromIndex,
                                     int toIndex,
                                     FloatComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(int[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(int[] a,
                                     int fromIndex,
                                     int toIndex,
                                     IntComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(long[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(long[] a,
                                     int fromIndex,
                                     int toIndex,
                                     LongComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort

        public static void mergeSort​(short[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • mergeSort

        public static void mergeSort​(short[] a,
                                     int fromIndex,
                                     int toIndex,
                                     ShortComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • mergeSort1

        private static void mergeSort1​(byte[] src,
                                       byte[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(byte[] src,
                                       byte[] dest,
                                       int low,
                                       int high,
                                       ByteComparator c)
      • mergeSort1

        private static void mergeSort1​(char[] src,
                                       char[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(char[] src,
                                       char[] dest,
                                       int low,
                                       int high,
                                       CharComparator c)
      • mergeSort1

        private static void mergeSort1​(double[] src,
                                       double[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(double[] src,
                                       double[] dest,
                                       int low,
                                       int high,
                                       DoubleComparator c)
      • mergeSort1

        private static void mergeSort1​(float[] src,
                                       float[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(float[] src,
                                       float[] dest,
                                       int low,
                                       int high,
                                       FloatComparator c)
      • mergeSort1

        private static void mergeSort1​(int[] src,
                                       int[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(int[] src,
                                       int[] dest,
                                       int low,
                                       int high,
                                       IntComparator c)
      • mergeSort1

        private static void mergeSort1​(long[] src,
                                       long[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(long[] src,
                                       long[] dest,
                                       int low,
                                       int high,
                                       LongComparator c)
      • mergeSort1

        private static void mergeSort1​(short[] src,
                                       short[] dest,
                                       int low,
                                       int high)
      • mergeSort1

        private static void mergeSort1​(short[] src,
                                       short[] dest,
                                       int low,
                                       int high,
                                       ShortComparator c)
      • mergeSort2

        private static void mergeSort2​(double[] a,
                                       int fromIndex,
                                       int toIndex)
      • mergeSort2

        private static void mergeSort2​(float[] a,
                                       int fromIndex,
                                       int toIndex)
      • mergeSortInPlace

        public static void mergeSortInPlace​(int[] a,
                                            int fromIndex,
                                            int toIndex)
        Sorts the specified range of the specified array of elements.

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • quickSort

        public static void quickSort​(byte[] a,
                                     int fromIndex,
                                     int toIndex,
                                     ByteComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(char[] a,
                                     int fromIndex,
                                     int toIndex,
                                     CharComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(double[] a,
                                     int fromIndex,
                                     int toIndex,
                                     DoubleComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(float[] a,
                                     int fromIndex,
                                     int toIndex,
                                     FloatComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(int[] a,
                                     int fromIndex,
                                     int toIndex,
                                     IntComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(long[] a,
                                     int fromIndex,
                                     int toIndex,
                                     LongComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(java.lang.Object[] a)
        Sorts the specified range of the receiver into ascending order, according to the natural ordering of its elements. All elements in this range must implement the Comparable interface. Furthermore, all elements in this range must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the array).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
      • quickSort

        public static void quickSort​(java.lang.Object[] a,
                                     int fromIndex,
                                     int toIndex)
        Sorts the specified range of the receiver into ascending order, according to the natural ordering of its elements. All elements in this range must implement the Comparable interface. Furthermore, all elements in this range must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the array).

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        Throws:
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
      • quickSort

        public static void quickSort​(java.lang.Object[] a,
                                     int fromIndex,
                                     int toIndex,
                                     java.util.Comparator c)
        Sorts the specified range of the specified array according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the receiver.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(java.lang.Object[] a,
                                     java.util.Comparator c)
        Sorts the specified array according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

        Parameters:
        a - the array to be sorted.
        c - the comparator to determine the order of the receiver.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort

        public static void quickSort​(short[] a,
                                     int fromIndex,
                                     int toIndex,
                                     ShortComparator c)
        Sorts the specified range of the specified array of elements according to the order induced by the specified comparator. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the range).

        This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

        The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

        Parameters:
        a - the array to be sorted.
        fromIndex - the index of the first element (inclusive) to be sorted.
        toIndex - the index of the last element (exclusive) to be sorted.
        c - the comparator to determine the order of the array.
        Throws:
        java.lang.ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.
        java.lang.IllegalArgumentException - if fromIndex > toIndex
        java.lang.ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
        See Also:
        Comparator
      • quickSort1

        private static void quickSort1​(byte[] x,
                                       int off,
                                       int len,
                                       ByteComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(char[] x,
                                       int off,
                                       int len,
                                       CharComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(double[] x,
                                       int off,
                                       int len,
                                       DoubleComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(float[] x,
                                       int off,
                                       int len,
                                       FloatComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(int[] x,
                                       int off,
                                       int len,
                                       IntComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(long[] x,
                                       int off,
                                       int len,
                                       LongComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(java.lang.Object[] x,
                                       int off,
                                       int len)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(java.lang.Object[] x,
                                       int off,
                                       int len,
                                       java.util.Comparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • quickSort1

        private static void quickSort1​(short[] x,
                                       int off,
                                       int len,
                                       ShortComparator comp)
        Sorts the specified sub-array of chars into ascending order.
      • rangeCheck

        private static void rangeCheck​(int arrayLen,
                                       int fromIndex,
                                       int toIndex)
        Check that fromIndex and toIndex are in range, and throw an appropriate exception if they aren't.
      • swap

        private static void swap​(byte[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(char[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(double[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(float[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(int[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(long[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(java.lang.Object[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • swap

        private static void swap​(short[] x,
                                 int a,
                                 int b)
        Swaps x[a] with x[b].
      • vecswap

        private static void vecswap​(byte[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(char[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(double[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(float[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(int[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(long[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(java.lang.Object[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
      • vecswap

        private static void vecswap​(short[] x,
                                    int a,
                                    int b,
                                    int n)
        Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].