Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math » [javadoc | source]
    1   /**
    2    * Licensed to the Apache Software Foundation (ASF) under one
    3    * or more contributor license agreements. See the NOTICE file
    4    * distributed with this work for additional information
    5    * regarding copyright ownership. The ASF licenses this file
    6    * to you under the Apache License, Version 2.0 (the
    7    * "License"); you may not use this file except in compliance
    8    * with the License. You may obtain a copy of the License at
    9    *
   10    * http://www.apache.org/licenses/LICENSE-2.0
   11    *
   12    * Unless required by applicable law or agreed to in writing,
   13    * software distributed under the License is distributed on an
   14    * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   15    * KIND, either express or implied. See the License for the
   16    * specific language governing permissions and limitations
   17    * under the License.
   18    */
   19   
   20   package org.apache.mahout.math;
   21   
   22   import java.util.Comparator;
   23   
   24   import org.apache.mahout.math.function.ByteComparator;
   25   import org.apache.mahout.math.function.CharComparator;
   26   import org.apache.mahout.math.function.DoubleComparator;
   27   import org.apache.mahout.math.function.FloatComparator;
   28   import org.apache.mahout.math.function.IntComparator;
   29   import org.apache.mahout.math.function.LongComparator;
   30   import org.apache.mahout.math.function.ShortComparator;
   31   
   32   public final class Sorting {
   33     
   34     /* Specifies when to switch to insertion sort */
   35     private static final int SIMPLE_LENGTH = 7;
   36     static final int SMALL = 7;
   37     
   38     private Sorting() {
   39     /* empty */
   40     }
   41     
   42     /**
   43      * Performs a binary search for the specified element in the specified
   44      * ascending sorted array. Searching in an unsorted array has an undefined
   45      * result. It's also undefined which element is found if there are multiple
   46      * occurrences of the same element.
   47      * 
   48      * @param array
   49      *          the sorted {@code byte} array to search.
   50      * @param value
   51      *          the {@code byte} element to find.
   52      * @param from
   53      *          the first index to sort, inclusive.
   54      * @param to
   55      *          the last index to sort, inclusive.
   56      * @return the non-negative index of the element, or a negative index which is
   57      *         {@code -index - 1} where the element would be inserted.
   58      */
   59     public static int binarySearchFromTo(byte[] array, byte value, int from,
   60         int to) {
   61       int mid = -1;
   62       while (from <= to) {
   63         mid = (from + to) >>> 1;
   64         if (value > array[mid]) {
   65           from = mid + 1;
   66         } else if (value == array[mid]) {
   67           return mid;
   68         } else {
   69           to = mid - 1;
   70         }
   71       }
   72       if (mid < 0) {
   73         return -1;
   74       }
   75       
   76       return -mid - (value < array[mid] ? 1 : 2);
   77     }
   78     
   79     /**
   80      * Performs a binary search for the specified element in the specified
   81      * ascending sorted array. Searching in an unsorted array has an undefined
   82      * result. It's also undefined which element is found if there are multiple
   83      * occurrences of the same element.
   84      * 
   85      * @param array
   86      *          the sorted {@code char} array to search.
   87      * @param value
   88      *          the {@code char} element to find.
   89      * @param from
   90      *          the first index to sort, inclusive.
   91      * @param to
   92      *          the last index to sort, inclusive.
   93      * @return the non-negative index of the element, or a negative index which is
   94      *         {@code -index - 1} where the element would be inserted.
   95      */
   96     public static int binarySearchFromTo(char[] array, char value, int from,
   97         int to) {
   98       int mid = -1;
   99       while (from <= to) {
  100         mid = (from + to) >>> 1;
  101         if (value > array[mid]) {
  102           from = mid + 1;
  103         } else if (value == array[mid]) {
  104           return mid;
  105         } else {
  106           to = mid - 1;
  107         }
  108       }
  109       if (mid < 0) {
  110         return -1;
  111       }
  112       return -mid - (value < array[mid] ? 1 : 2);
  113     }
  114     
  115     /**
  116      * Performs a binary search for the specified element in the specified
  117      * ascending sorted array. Searching in an unsorted array has an undefined
  118      * result. It's also undefined which element is found if there are multiple
  119      * occurrences of the same element.
  120      * 
  121      * @param array
  122      *          the sorted {@code double} array to search.
  123      * @param value
  124      *          the {@code double} element to find.
  125      * @param from
  126      *          the first index to sort, inclusive.
  127      * @param to
  128      *          the last index to sort, inclusive.
  129      * @return the non-negative index of the element, or a negative index which is
  130      *         {@code -index - 1} where the element would be inserted.
  131      */
  132     public static int binarySearchFromTo(double[] array, double value, int from,
  133         int to) {
  134       long longBits = Double.doubleToLongBits(value);
  135       int mid = -1;
  136       while (from <= to) {
  137         mid = (from + to) >>> 1;
  138         if (lessThan(array[mid], value)) {
  139           from = mid + 1;
  140         } else if (longBits == Double.doubleToLongBits(array[mid])) {
  141           return mid;
  142         } else {
  143           to = mid - 1;
  144         }
  145       }
  146       if (mid < 0) {
  147         return -1;
  148       }
  149       return -mid - (lessThan(value, array[mid]) ? 1 : 2);
  150     }
  151     
  152     /**
  153      * Performs a binary search for the specified element in the specified
  154      * ascending sorted array. Searching in an unsorted array has an undefined
  155      * result. It's also undefined which element is found if there are multiple
  156      * occurrences of the same element.
  157      * 
  158      * @param array
  159      *          the sorted {@code float} array to search.
  160      * @param value
  161      *          the {@code float} element to find.
  162      * @param from
  163      *          the first index to sort, inclusive.
  164      * @param to
  165      *          the last index to sort, inclusive.
  166      * @return the non-negative index of the element, or a negative index which is
  167      *         {@code -index - 1} where the element would be inserted.
  168      */
  169     public static int binarySearchFromTo(float[] array, float value, int from,
  170         int to) {
  171       int intBits = Float.floatToIntBits(value);
  172       int mid = -1;
  173       while (from <= to) {
  174         mid = (from + to) >>> 1;
  175         if (lessThan(array[mid], value)) {
  176           from = mid + 1;
  177         } else if (intBits == Float.floatToIntBits(array[mid])) {
  178           return mid;
  179         } else {
  180           to = mid - 1;
  181         }
  182       }
  183       if (mid < 0) {
  184         return -1;
  185       }
  186       return -mid - (lessThan(value, array[mid]) ? 1 : 2);
  187     }
  188     
  189     /**
  190      * Performs a binary search for the specified element in the specified
  191      * ascending sorted array. Searching in an unsorted array has an undefined
  192      * result. It's also undefined which element is found if there are multiple
  193      * occurrences of the same element.
  194      * 
  195      * @param array
  196      *          the sorted {@code int} array to search.
  197      * @param value
  198      *          the {@code int} element to find.
  199      * @param from
  200      *          the first index to sort, inclusive.
  201      * @param to
  202      *          the last index to sort, inclusive.
  203      * @return the non-negative index of the element, or a negative index which is
  204      *         {@code -index - 1} where the element would be inserted.
  205      */
  206     public static int binarySearchFromTo(int[] array, int value, int from, int to) {
  207       int mid = -1;
  208       while (from <= to) {
  209         mid = (from + to) >>> 1;
  210         if (value > array[mid]) {
  211           from = mid + 1;
  212         } else if (value == array[mid]) {
  213           return mid;
  214         } else {
  215           to = mid - 1;
  216         }
  217       }
  218       if (mid < 0) {
  219         return -1;
  220       }
  221       return -mid - (value < array[mid] ? 1 : 2);
  222     }
  223     
  224     /**
  225      * Performs a binary search for the specified element in the specified
  226      * ascending sorted array. Searching in an unsorted array has an undefined
  227      * result. It's also undefined which element is found if there are multiple
  228      * occurrences of the same element.
  229      * 
  230      * @param array
  231      *          the sorted {@code long} array to search.
  232      * @param value
  233      *          the {@code long} element to find.
  234      * @param from
  235      *          the first index to sort, inclusive.
  236      * @param to
  237      *          the last index to sort, inclusive.
  238      * @return the non-negative index of the element, or a negative index which is
  239      *         {@code -index - 1} where the element would be inserted.
  240      */
  241     public static int binarySearchFromTo(long[] array, long value, int from, int to) {
  242       int mid = -1;
  243       while (from <= to) {
  244         mid = (from + to) >>> 1;
  245         if (value > array[mid]) {
  246           from = mid + 1;
  247         } else if (value == array[mid]) {
  248           return mid;
  249         } else {
  250           to = mid - 1;
  251         }
  252       }
  253       if (mid < 0) {
  254         return -1;
  255       }
  256       return -mid - (value < array[mid] ? 1 : 2);
  257     }
  258     
  259     /**
  260      * Performs a binary search for the specified element in the specified
  261      * ascending sorted array. Searching in an unsorted array has an undefined
  262      * result. It's also undefined which element is found if there are multiple
  263      * occurrences of the same element.
  264      * 
  265      * @param array
  266      *          the sorted {@code Object} array to search.
  267      * @param object
  268      *          the {@code Object} element to find
  269      * @param from
  270      *          the first index to sort, inclusive.
  271      * @param to
  272      *          the last index to sort, inclusive.
  273      * @return the non-negative index of the element, or a negative index which is
  274      *         {@code -index - 1} where the element would be inserted.
  275      * 
  276      */
  277     public static <T extends Comparable<T>> int binarySearchFromTo(T[] array,
  278         T object, int from, int to) {
  279       if (array.length == 0) {
  280         return -1;
  281       }
  282       
  283       int mid = 0, result = 0;
  284       while (from <= to) {
  285         mid = (from + to) >>> 1;
  286         if ((result = array[mid].compareTo(object)) < 0) {
  287           from = mid + 1;
  288         } else if (result == 0) {
  289           return mid;
  290         } else {
  291           to = mid - 1;
  292         }
  293       }
  294       return -mid - (result >= 0 ? 1 : 2);
  295     }
  296     
  297     /**
  298      * Performs a binary search for the specified element in the specified
  299      * ascending sorted array using the {@code Comparator} to compare elements.
  300      * Searching in an unsorted array has an undefined result. It's also undefined
  301      * which element is found if there are multiple occurrences of the same
  302      * element.
  303      * 
  304      * @param array
  305      *          the sorted array to search
  306      * @param object
  307      *          the element to find
  308      * @param from
  309      *          the first index to sort, inclusive.
  310      * @param to
  311      *          the last index to sort, inclusive.
  312      * @param comparator
  313      *          the {@code Comparator} used to compare the elements.
  314      * @return the non-negative index of the element, or a negative index which
  315      */
  316     public static <T> int binarySearchFromTo(T[] array, T object, int from,
  317         int to, Comparator<? super T> comparator) {
  318       int mid = 0, result = 0;
  319       while (from <= to) {
  320         mid = (from + to) >>> 1;
  321         if ((result = comparator.compare(array[mid], object)) < 0) {
  322           from = mid + 1;
  323         } else if (result == 0) {
  324           return mid;
  325         } else {
  326           to = mid - 1;
  327         }
  328       }
  329       return -mid - (result >= 0 ? 1 : 2);
  330     }
  331     
  332     /**
  333      * Performs a binary search for the specified element in the specified
  334      * ascending sorted array. Searching in an unsorted array has an undefined
  335      * result. It's also undefined which element is found if there are multiple
  336      * occurrences of the same element.
  337      * 
  338      * @param array
  339      *          the sorted {@code short} array to search.
  340      * @param value
  341      *          the {@code short} element to find.
  342      * @param from
  343      *          the first index to sort, inclusive.
  344      * @param to
  345      *          the last index to sort, inclusive.
  346      * @return the non-negative index of the element, or a negative index which is
  347      *         {@code -index - 1} where the element would be inserted.
  348      */
  349     public static int binarySearchFromTo(short[] array, short value, int from, int to) {
  350       int mid = -1;
  351       while (from <= to) {
  352         mid = (from + to) >>> 1;
  353         if (value > array[mid]) {
  354           from = mid + 1;
  355         } else if (value == array[mid]) {
  356           return mid;
  357         } else {
  358           to = mid - 1;
  359         }
  360       }
  361       if (mid < 0) {
  362         return -1;
  363       }
  364       return -mid - (value < array[mid] ? 1 : 2);
  365     }
  366     
  367     private static boolean lessThan(double double1, double double2) {
  368       // A slightly specialized version of
  369       // Double.compare(double1, double2) < 0.
  370       
  371       // Non-zero and non-NaN checking.
  372       if (double1 < double2) {
  373         return true;
  374       }
  375       if (double1 > double2) {
  376         return false;
  377       }
  378       if (double1 == double2 && double1 != 0.0) {
  379         return false;
  380       }
  381       
  382       // NaNs are equal to other NaNs and larger than any other double.
  383       if (Double.isNaN(double1)) {
  384         return false;
  385       } else if (Double.isNaN(double2)) {
  386         return true;
  387       }
  388       
  389       // Deal with +0.0 and -0.0.
  390       long d1 = Double.doubleToRawLongBits(double1);
  391       long d2 = Double.doubleToRawLongBits(double2);
  392       return d1 < d2;
  393     }
  394     
  395     private static boolean lessThan(float float1, float float2) {
  396       // A slightly specialized version of Float.compare(float1, float2) < 0.
  397       
  398       // Non-zero and non-NaN checking.
  399       if (float1 < float2) {
  400         return true;
  401       }
  402       if (float1 > float2) {
  403         return false;
  404       }
  405       if (float1 == float2 && float1 != 0.0f) {
  406         return false;
  407       }
  408       
  409       // NaNs are equal to other NaNs and larger than any other float
  410       if (Float.isNaN(float1)) {
  411         return false;
  412       } else if (Float.isNaN(float2)) {
  413         return true;
  414       }
  415       
  416       // Deal with +0.0 and -0.0
  417       int f1 = Float.floatToRawIntBits(float1);
  418       int f2 = Float.floatToRawIntBits(float2);
  419       return f1 < f2;
  420     }
  421     
  422     private static <T> int med3(T[] array, int a, int b, int c, Comparator<T> comp) {
  423       T x = array[a], y = array[b], z = array[c];
  424       int comparisonxy = comp.compare(x, y);
  425       int comparisonxz = comp.compare(x, z);
  426       int comparisonyz = comp.compare(y, z);
  427       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  428           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  429           : (comparisonxz > 0 ? c : a));
  430     }
  431     
  432     private static int med3(byte[] array, int a, int b, int c, ByteComparator comp) {
  433       byte x = array[a], y = array[b], z = array[c];
  434       int comparisonxy = comp.compare(x, y);
  435       int comparisonxz = comp.compare(x, z);
  436       int comparisonyz = comp.compare(y, z);
  437       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  438           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  439           : (comparisonxz > 0 ? c : a));
  440     }
  441     
  442     private static int med3(char[] array, int a, int b, int c, CharComparator comp) {
  443       char x = array[a], y = array[b], z = array[c];
  444       int comparisonxy = comp.compare(x, y);
  445       int comparisonxz = comp.compare(x, z);
  446       int comparisonyz = comp.compare(y, z);
  447       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  448           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  449           : (comparisonxz > 0 ? c : a));
  450     }
  451     
  452     private static int med3(double[] array, int a, int b, int c,
  453         DoubleComparator comp) {
  454       double x = array[a], y = array[b], z = array[c];
  455       int comparisonxy = comp.compare(x, y);
  456       int comparisonxz = comp.compare(x, z);
  457       int comparisonyz = comp.compare(y, z);
  458       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  459           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  460           : (comparisonxz > 0 ? c : a));
  461     }
  462     
  463     private static int med3(float[] array, int a, int b, int c,
  464         FloatComparator comp) {
  465       float x = array[a], y = array[b], z = array[c];
  466       int comparisonxy = comp.compare(x, y);
  467       int comparisonxz = comp.compare(x, z);
  468       int comparisonyz = comp.compare(y, z);
  469       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  470           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  471           : (comparisonxz > 0 ? c : a));
  472     }
  473     
  474     private static int med3(int[] array, int a, int b, int c, IntComparator comp) {
  475       int x = array[a], y = array[b], z = array[c];
  476       int comparisonxy = comp.compare(x, y);
  477       int comparisonxz = comp.compare(x, z);
  478       int comparisonyz = comp.compare(y, z);
  479       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  480           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  481           : (comparisonxz > 0 ? c : a));
  482     }
  483     
  484     /**
  485      * This is used for 'external' sorting. The comparator takes <em>indices</em>,
  486      * not values, and compares the external values found at those indices.
  487      * @param a
  488      * @param b
  489      * @param c
  490      * @param comp
  491      * @return
  492      */
  493     private static int med3(int a, int b, int c, IntComparator comp) {
  494       int comparisonab = comp.compare(a, b);
  495       int comparisonac = comp.compare(a, c);
  496       int comparisonbc = comp.compare(b, c);
  497       return comparisonab < 0 ?
  498           (comparisonbc < 0 ? b : (comparisonac < 0 ? c : a)) :
  499           (comparisonbc > 0 ? b : (comparisonac > 0 ? c : a));
  500     }
  501     
  502     private static int med3(long[] array, int a, int b, int c, LongComparator comp) {
  503       long x = array[a], y = array[b], z = array[c];
  504       int comparisonxy = comp.compare(x, y);
  505       int comparisonxz = comp.compare(x, z);
  506       int comparisonyz = comp.compare(y, z);
  507       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  508           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  509           : (comparisonxz > 0 ? c : a));
  510     }
  511     
  512     private static int med3(short[] array, int a, int b, int c,
  513         ShortComparator comp) {
  514       short x = array[a], y = array[b], z = array[c];
  515       int comparisonxy = comp.compare(x, y);
  516       int comparisonxz = comp.compare(x, z);
  517       int comparisonyz = comp.compare(y, z);
  518       return comparisonxy < 0 ? (comparisonyz < 0 ? b
  519           : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
  520           : (comparisonxz > 0 ? c : a));
  521     }
  522     
  523     /**
  524      * Sorts the specified range in the array in a specified order.
  525      * 
  526      * @param array
  527      *          the {@code byte} array to be sorted.
  528      * @param start
  529      *          the start index to sort.
  530      * @param end
  531      *          the last + 1 index to sort.
  532      * @param comp
  533      *          the comparison that determines the sort.
  534      * @throws IllegalArgumentException
  535      *           if {@code start > end}.
  536      * @throws ArrayIndexOutOfBoundsException
  537      *           if {@code start < 0} or {@code end > array.length}.
  538      */
  539     public static void quickSort(byte[] array, int start, int end,
  540         ByteComparator comp) {
  541       if (array == null) {
  542         throw new NullPointerException();
  543       }
  544       checkBounds(array.length, start, end);
  545       quickSort0(start, end, array, comp);
  546     }
  547     
  548     private static void checkBounds(int arrLength, int start, int end) {
  549       if (start > end) {
  550         // K0033=Start index ({0}) is greater than end index ({1})
  551         throw new IllegalArgumentException("Start index " + start
  552             + " is greater than end index " + end);
  553       }
  554       if (start < 0) {
  555         throw new ArrayIndexOutOfBoundsException("Array index out of range "
  556             + start);
  557       }
  558       if (end > arrLength) {
  559         throw new ArrayIndexOutOfBoundsException("Array index out of range "
  560             + end);
  561       }
  562     }
  563     
  564     private static void quickSort0(int start, int end, byte[] array,
  565         ByteComparator comp) {
  566       byte temp;
  567       int length = end - start;
  568       if (length < 7) {
  569         for (int i = start + 1; i < end; i++) {
  570           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
  571             temp = array[j];
  572             array[j] = array[j - 1];
  573             array[j - 1] = temp;
  574           }
  575         }
  576         return;
  577       }
  578       int middle = (start + end) / 2;
  579       if (length > 7) {
  580         int bottom = start;
  581         int top = end - 1;
  582         if (length > 40) {
  583           length /= 8;
  584           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
  585               comp);
  586           middle = med3(array, middle - length, middle, middle + length, comp);
  587           top = med3(array, top - (2 * length), top - length, top, comp);
  588         }
  589         middle = med3(array, bottom, middle, top, comp);
  590       }
  591       byte partionValue = array[middle];
  592       int a, b, c, d;
  593       a = b = start;
  594       c = d = end - 1;
  595       while (true) {
  596         int comparison;
  597         while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
  598           if (comparison == 0) {
  599             temp = array[a];
  600             array[a++] = array[b];
  601             array[b] = temp;
  602           }
  603           b++;
  604         }
  605         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
  606           if (comparison == 0) {
  607             temp = array[c];
  608             array[c] = array[d];
  609             array[d--] = temp;
  610           }
  611           c--;
  612         }
  613         if (b > c) {
  614           break;
  615         }
  616         temp = array[b];
  617         array[b++] = array[c];
  618         array[c--] = temp;
  619       }
  620       length = a - start < b - a ? a - start : b - a;
  621       int l = start;
  622       int h = b - length;
  623       while (length-- > 0) {
  624         temp = array[l];
  625         array[l++] = array[h];
  626         array[h++] = temp;
  627       }
  628       length = d - c < end - 1 - d ? d - c : end - 1 - d;
  629       l = b;
  630       h = end - length;
  631       while (length-- > 0) {
  632         temp = array[l];
  633         array[l++] = array[h];
  634         array[h++] = temp;
  635       }
  636       if ((length = b - a) > 0) {
  637         quickSort0(start, start + length, array, comp);
  638       }
  639       if ((length = d - c) > 0) {
  640         quickSort0(end - length, end, array, comp);
  641       }
  642     }
  643   
  644     
  645     /**
  646      * Sorts some external data with QuickSort.
  647      * 
  648      * @param start
  649      *          the start index to sort.
  650      * @param end
  651      *          the last + 1 index to sort.
  652      * @param comp
  653      *          the comparator.
  654      * @param swap an object that can exchange the positions of two items.
  655      * @throws IllegalArgumentException
  656      *           if {@code start > end}.
  657      * @throws ArrayIndexOutOfBoundsException
  658      *           if {@code start < 0} or {@code end > array.length}.
  659      */
  660     public static void quickSort(int start, int end, IntComparator comp, Swapper swap) {
  661       checkBounds(end+1, start, end);
  662       quickSort0(start, end, comp, swap);
  663     }
  664     
  665     private static void quickSort0(int start, int end, IntComparator comp, Swapper swap) {
  666       int length = end - start;
  667       if (length < 7) {
  668         insertionSort(start, end, comp, swap);
  669         return;
  670       }
  671       int middle = (start + end) / 2;
  672       if (length > 7) {
  673         int bottom = start;
  674         int top = end - 1;
  675         if (length > 40) {
  676           // for lots of data, bottom, middle and top are medians near the beginning, middle or end of the data
  677           int skosh = length / 8;
  678           bottom = med3(bottom, bottom + skosh, bottom + (2 * skosh), comp);
  679           middle = med3(middle - skosh, middle, middle + skosh, comp);
  680           top = med3(top - (2 * skosh), top - skosh, top, comp);
  681         }
  682         middle = med3(bottom, middle, top, comp);
  683       }
  684   
  685       int partitionIndex = middle; // an index, not a value.
  686       
  687       // regions from a to b and from c to d are what we will recursively sort
  688       int a, b, c, d;
  689       a = b = start;
  690       c = d = end - 1;
  691       while (b <= c) {
  692         // copy all values equal to the partition value to before a..b.  In the process, advance b
  693         // as long as values less than the partition or equal are found, also stop when a..b collides with c..d
  694         int comparison;
  695         while (b <= c && (comparison = comp.compare(b, partitionIndex)) <= 0) {
  696           if (comparison == 0) {
  697             if (a == partitionIndex) {
  698               partitionIndex = b;
  699             }
  700             else if (b == partitionIndex) {
  701               partitionIndex = a;
  702             }
  703             swap.swap(a, b);
  704             a++;
  705           }
  706           b++;
  707         }
  708         // at this point [start..a) has partition values, [a..b) has values < partition
  709         // also, either b>c or v[b] > partition value
  710   
  711         while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
  712           if (comparison == 0) {
  713             if (c == partitionIndex) {
  714               partitionIndex = d;
  715             } else if (d == partitionIndex) {
  716               partitionIndex = c;
  717             }
  718             swap.swap(c, d);
  719   
  720             d--;
  721           }
  722           c--;
  723         }
  724         // now we also know that [d..end] contains partition values,
  725         // [c..d) contains values > partition value
  726         // also, either b>c or (v[b] > partition OR v[c] < partition)
  727   
  728         if (b <= c) {
  729           // v[b] > partition OR v[c] < partition
  730           // swapping will let us continue to grow the two regions
  731           if (c == partitionIndex) {
  732             partitionIndex = b;
  733           } else if (b == partitionIndex) {
  734             partitionIndex = d;
  735           }
  736           swap.swap(b, c);
  737           b++;
  738           c--;
  739         }
  740       }
  741       // now we know
  742       // b = c+1
  743       // [start..a) and [d..end) contain partition value
  744       // all of [a..b) are less than partition
  745       // all of [c..d) are greater than partition
  746   
  747       // shift [a..b) to beginning
  748       length = Math.min(a - start, b - a);
  749       int l = start;
  750       int h = b - length;
  751       while (length-- > 0) {
  752         swap.swap(l, h);
  753         l++;
  754         h++;
  755       }
  756   
  757       // shift [c..d) to end
  758       length = Math.min(d - c, end - 1 - d);
  759       l = b;
  760       h = end - length;
  761        while (length-- > 0) {
  762         swap.swap(l, h);
  763         l++;
  764         h++;
  765       }
  766   
  767       // recurse left and right
  768       length = b - a;
  769       if (length > 0) {
  770         quickSort0(start, start + length, comp, swap);
  771       }
  772   
  773       length = d - c;
  774       if (length > 0) {
  775         quickSort0(end - length, end, comp, swap);
  776       }
  777     }
  778   
  779     /**
  780      * In-place insertion sort that is fast for pre-sorted data.
  781      *
  782      * @param start Where to start sorting (inclusive)
  783      * @param end   Where to stop (exclusive)
  784      * @param comp  Sort order.
  785      * @param swap  How to swap items.
  786      */
  787     private static void insertionSort(int start, int end, IntComparator comp, Swapper swap) {
  788       for (int i = start + 1; i < end; i++) {
  789         for (int j = i; j > start && comp.compare(j - 1, j) > 0; j--) {
  790           swap.swap(j - 1, j);
  791         }
  792       }
  793     }
  794     /**
  795      * Sorts the specified range in the array in a specified order.
  796      * 
  797      * @param array
  798      *          the {@code char} array to be sorted.
  799      * @param start
  800      *          the start index to sort.
  801      * @param end
  802      *          the last + 1 index to sort.
  803      * @throws IllegalArgumentException
  804      *           if {@code start > end}.
  805      * @throws ArrayIndexOutOfBoundsException
  806      *           if {@code start < 0} or {@code end > array.length}.
  807      */
  808     public static void quickSort(char[] array, int start, int end,
  809         CharComparator comp) {
  810       if (array == null) {
  811         throw new NullPointerException();
  812       }
  813       checkBounds(array.length, start, end);
  814       quickSort0(start, end, array, comp);
  815     }
  816     
  817     private static void quickSort0(int start, int end, char[] array,
  818         CharComparator comp) {
  819       char temp;
  820       int length = end - start;
  821       if (length < 7) {
  822         for (int i = start + 1; i < end; i++) {
  823           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
  824             temp = array[j];
  825             array[j] = array[j - 1];
  826             array[j - 1] = temp;
  827           }
  828         }
  829         return;
  830       }
  831       int middle = (start + end) / 2;
  832       if (length > 7) {
  833         int bottom = start;
  834         int top = end - 1;
  835         if (length > 40) {
  836           length /= 8;
  837           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
  838               comp);
  839           middle = med3(array, middle - length, middle, middle + length, comp);
  840           top = med3(array, top - (2 * length), top - length, top, comp);
  841         }
  842         middle = med3(array, bottom, middle, top, comp);
  843       }
  844       char partionValue = array[middle];
  845       int a, b, c, d;
  846       a = b = start;
  847       c = d = end - 1;
  848       while (true) {
  849         int comparison;
  850         while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
  851           if (comparison == 0) {
  852             temp = array[a];
  853             array[a++] = array[b];
  854             array[b] = temp;
  855           }
  856           b++;
  857         }
  858         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
  859           if (comparison == 0) {
  860             temp = array[c];
  861             array[c] = array[d];
  862             array[d--] = temp;
  863           }
  864           c--;
  865         }
  866         if (b > c) {
  867           break;
  868         }
  869         temp = array[b];
  870         array[b++] = array[c];
  871         array[c--] = temp;
  872       }
  873       length = a - start < b - a ? a - start : b - a;
  874       int l = start;
  875       int h = b - length;
  876       while (length-- > 0) {
  877         temp = array[l];
  878         array[l++] = array[h];
  879         array[h++] = temp;
  880       }
  881       length = d - c < end - 1 - d ? d - c : end - 1 - d;
  882       l = b;
  883       h = end - length;
  884       while (length-- > 0) {
  885         temp = array[l];
  886         array[l++] = array[h];
  887         array[h++] = temp;
  888       }
  889       if ((length = b - a) > 0) {
  890         quickSort0(start, start + length, array, comp);
  891       }
  892       if ((length = d - c) > 0) {
  893         quickSort0(end - length, end, array, comp);
  894       }
  895     }
  896     
  897     /**
  898      * Sorts the specified range in the array in a specified order.
  899      * 
  900      * @param array
  901      *          the {@code double} array to be sorted.
  902      * @param start
  903      *          the start index to sort.
  904      * @param end
  905      *          the last + 1 index to sort.
  906      * @param comp
  907      *          the comparison.
  908      * @throws IllegalArgumentException
  909      *           if {@code start > end}.
  910      * @throws ArrayIndexOutOfBoundsException
  911      *           if {@code start < 0} or {@code end > array.length}.
  912      * @see Double#compareTo(Double)
  913      */
  914     public static void quickSort(double[] array, int start, int end,
  915         DoubleComparator comp) {
  916       if (array == null) {
  917         throw new NullPointerException();
  918       }
  919       checkBounds(array.length, start, end);
  920       quickSort0(start, end, array, comp);
  921     }
  922     
  923     private static void quickSort0(int start, int end, double[] array,
  924         DoubleComparator comp) {
  925       double temp;
  926       int length = end - start;
  927       if (length < 7) {
  928         for (int i = start + 1; i < end; i++) {
  929           for (int j = i; j > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
  930             temp = array[j];
  931             array[j] = array[j - 1];
  932             array[j - 1] = temp;
  933           }
  934         }
  935         return;
  936       }
  937       int middle = (start + end) / 2;
  938       if (length > 7) {
  939         int bottom = start;
  940         int top = end - 1;
  941         if (length > 40) {
  942           length /= 8;
  943           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
  944               comp);
  945           middle = med3(array, middle - length, middle, middle + length, comp);
  946           top = med3(array, top - (2 * length), top - length, top, comp);
  947         }
  948         middle = med3(array, bottom, middle, top, comp);
  949       }
  950       double partionValue = array[middle];
  951       int a, b, c, d;
  952       a = b = start;
  953       c = d = end - 1;
  954       while (true) {
  955         int comparison;
  956         while (b <= c && (comparison = comp.compare(partionValue, array[b])) >= 0) {
  957           if (comparison == 0) {
  958             temp = array[a];
  959             array[a++] = array[b];
  960             array[b] = temp;
  961           }
  962           b++;
  963         }
  964         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
  965           if (comparison == 0) {
  966             temp = array[c];
  967             array[c] = array[d];
  968             array[d--] = temp;
  969           }
  970           c--;
  971         }
  972         if (b > c) {
  973           break;
  974         }
  975         temp = array[b];
  976         array[b++] = array[c];
  977         array[c--] = temp;
  978       }
  979       length = a - start < b - a ? a - start : b - a;
  980       int l = start;
  981       int h = b - length;
  982       while (length-- > 0) {
  983         temp = array[l];
  984         array[l++] = array[h];
  985         array[h++] = temp;
  986       }
  987       length = d - c < end - 1 - d ? d - c : end - 1 - d;
  988       l = b;
  989       h = end - length;
  990       while (length-- > 0) {
  991         temp = array[l];
  992         array[l++] = array[h];
  993         array[h++] = temp;
  994       }
  995       if ((length = b - a) > 0) {
  996         quickSort0(start, start + length, array, comp);
  997       }
  998       if ((length = d - c) > 0) {
  999         quickSort0(end - length, end, array, comp);
 1000       }
 1001     }
 1002     
 1003     /**
 1004      * Sorts the specified range in the array in a specified order.
 1005      * 
 1006      * @param array
 1007      *          the {@code float} array to be sorted.
 1008      * @param start
 1009      *          the start index to sort.
 1010      * @param end
 1011      *          the last + 1 index to sort.
 1012      * @param comp
 1013      *          the comparator.
 1014      * @throws IllegalArgumentException
 1015      *           if {@code start > end}.
 1016      * @throws ArrayIndexOutOfBoundsException
 1017      *           if {@code start < 0} or {@code end > array.length}.
 1018      */
 1019     public static void quickSort(float[] array, int start, int end,
 1020         FloatComparator comp) {
 1021       if (array == null) {
 1022         throw new NullPointerException();
 1023       }
 1024       checkBounds(array.length, start, end);
 1025       quickSort0(start, end, array, comp);
 1026     }
 1027     
 1028     private static void quickSort0(int start, int end, float[] array,
 1029         FloatComparator comp) {
 1030       float temp;
 1031       int length = end - start;
 1032       if (length < 7) {
 1033         for (int i = start + 1; i < end; i++) {
 1034           for (int j = i; j > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
 1035             temp = array[j];
 1036             array[j] = array[j - 1];
 1037             array[j - 1] = temp;
 1038           }
 1039         }
 1040         return;
 1041       }
 1042       int middle = (start + end) / 2;
 1043       if (length > 7) {
 1044         int bottom = start;
 1045         int top = end - 1;
 1046         if (length > 40) {
 1047           length /= 8;
 1048           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
 1049               comp);
 1050           middle = med3(array, middle - length, middle, middle + length, comp);
 1051           top = med3(array, top - (2 * length), top - length, top, comp);
 1052         }
 1053         middle = med3(array, bottom, middle, top, comp);
 1054       }
 1055       float partionValue = array[middle];
 1056       int a, b, c, d;
 1057       a = b = start;
 1058       c = d = end - 1;
 1059       while (true) {
 1060         int comparison;
 1061         while (b <= c && (comparison = comp.compare(partionValue, array[b])) >= 0) {
 1062           if (comparison == 0) {
 1063             temp = array[a];
 1064             array[a++] = array[b];
 1065             array[b] = temp;
 1066           }
 1067           b++;
 1068         }
 1069         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
 1070           if (comparison == 0) {
 1071             temp = array[c];
 1072             array[c] = array[d];
 1073             array[d--] = temp;
 1074           }
 1075           c--;
 1076         }
 1077         if (b > c) {
 1078           break;
 1079         }
 1080         temp = array[b];
 1081         array[b++] = array[c];
 1082         array[c--] = temp;
 1083       }
 1084       length = a - start < b - a ? a - start : b - a;
 1085       int l = start;
 1086       int h = b - length;
 1087       while (length-- > 0) {
 1088         temp = array[l];
 1089         array[l++] = array[h];
 1090         array[h++] = temp;
 1091       }
 1092       length = d - c < end - 1 - d ? d - c : end - 1 - d;
 1093       l = b;
 1094       h = end - length;
 1095       while (length-- > 0) {
 1096         temp = array[l];
 1097         array[l++] = array[h];
 1098         array[h++] = temp;
 1099       }
 1100       if ((length = b - a) > 0) {
 1101         quickSort0(start, start + length, array, comp);
 1102       }
 1103       if ((length = d - c) > 0) {
 1104         quickSort0(end - length, end, array, comp);
 1105       }
 1106     }
 1107     
 1108     /**
 1109      * Sorts the specified range in the array in a specified order.
 1110      * 
 1111      * @param array
 1112      *          the {@code int} array to be sorted.
 1113      * @param start
 1114      *          the start index to sort.
 1115      * @param end
 1116      *          the last + 1 index to sort.
 1117      * @param comp
 1118      *          the comparator.
 1119      * @throws IllegalArgumentException
 1120      *           if {@code start > end}.
 1121      * @throws ArrayIndexOutOfBoundsException
 1122      *           if {@code start < 0} or {@code end > array.length}.
 1123      */
 1124     public static void quickSort(int[] array, int start, int end,
 1125         IntComparator comp) {
 1126       if (array == null) {
 1127         throw new NullPointerException();
 1128       }
 1129       checkBounds(array.length, start, end);
 1130       quickSort0(start, end, array, comp);
 1131     }
 1132     
 1133     private static void quickSort0(int start, int end, int[] array,
 1134         IntComparator comp) {
 1135       int temp;
 1136       int length = end - start;
 1137       if (length < 7) {
 1138         for (int i = start + 1; i < end; i++) {
 1139           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
 1140             temp = array[j];
 1141             array[j] = array[j - 1];
 1142             array[j - 1] = temp;
 1143           }
 1144         }
 1145         return;
 1146       }
 1147       int middle = (start + end) / 2;
 1148       if (length > 7) {
 1149         int bottom = start;
 1150         int top = end - 1;
 1151         if (length > 40) {
 1152           length /= 8;
 1153           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
 1154               comp);
 1155           middle = med3(array, middle - length, middle, middle + length, comp);
 1156           top = med3(array, top - (2 * length), top - length, top, comp);
 1157         }
 1158         middle = med3(array, bottom, middle, top, comp);
 1159       }
 1160       int partionValue = array[middle];
 1161       int a, b, c, d;
 1162       a = b = start;
 1163       c = d = end - 1;
 1164       while (true) {
 1165         int comparison;
 1166         while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
 1167           if (comparison == 0) {
 1168             temp = array[a];
 1169             array[a++] = array[b];
 1170             array[b] = temp;
 1171           }
 1172           b++;
 1173         }
 1174         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
 1175           if (comparison == 0) {
 1176             temp = array[c];
 1177             array[c] = array[d];
 1178             array[d--] = temp;
 1179           }
 1180           c--;
 1181         }
 1182         if (b > c) {
 1183           break;
 1184         }
 1185         temp = array[b];
 1186         array[b++] = array[c];
 1187         array[c--] = temp;
 1188       }
 1189       length = a - start < b - a ? a - start : b - a;
 1190       int l = start;
 1191       int h = b - length;
 1192       while (length-- > 0) {
 1193         temp = array[l];
 1194         array[l++] = array[h];
 1195         array[h++] = temp;
 1196       }
 1197       length = d - c < end - 1 - d ? d - c : end - 1 - d;
 1198       l = b;
 1199       h = end - length;
 1200       while (length-- > 0) {
 1201         temp = array[l];
 1202         array[l++] = array[h];
 1203         array[h++] = temp;
 1204       }
 1205       if ((length = b - a) > 0) {
 1206         quickSort0(start, start + length, array, comp);
 1207       }
 1208       if ((length = d - c) > 0) {
 1209         quickSort0(end - length, end, array, comp);
 1210       }
 1211     }
 1212     
 1213     /**
 1214      * Sorts the specified range in the array in a specified order.
 1215      * 
 1216      * @param array
 1217      *          the {@code long} array to be sorted.
 1218      * @param start
 1219      *          the start index to sort.
 1220      * @param end
 1221      *          the last + 1 index to sort.
 1222      * @param comp
 1223      *          the comparator.
 1224      * @throws IllegalArgumentException
 1225      *           if {@code start > end}.
 1226      * @throws ArrayIndexOutOfBoundsException
 1227      *           if {@code start < 0} or {@code end > array.length}.
 1228      */
 1229     public static void quickSort(long[] array, int start, int end,
 1230         LongComparator comp) {
 1231       if (array == null) {
 1232         throw new NullPointerException();
 1233       }
 1234       checkBounds(array.length, start, end);
 1235       quickSort0(start, end, array, comp);
 1236     }
 1237     
 1238     private static void quickSort0(int start, int end, long[] array,
 1239         LongComparator comp) {
 1240       long temp;
 1241       int length = end - start;
 1242       if (length < 7) {
 1243         for (int i = start + 1; i < end; i++) {
 1244           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
 1245             temp = array[j];
 1246             array[j] = array[j - 1];
 1247             array[j - 1] = temp;
 1248           }
 1249         }
 1250         return;
 1251       }
 1252       int middle = (start + end) / 2;
 1253       if (length > 7) {
 1254         int bottom = start;
 1255         int top = end - 1;
 1256         if (length > 40) {
 1257           length /= 8;
 1258           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
 1259               comp);
 1260           middle = med3(array, middle - length, middle, middle + length, comp);
 1261           top = med3(array, top - (2 * length), top - length, top, comp);
 1262         }
 1263         middle = med3(array, bottom, middle, top, comp);
 1264       }
 1265       long partionValue = array[middle];
 1266       int a, b, c, d;
 1267       a = b = start;
 1268       c = d = end - 1;
 1269       while (true) {
 1270         int comparison;
 1271         while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
 1272           if (comparison == 0) {
 1273             temp = array[a];
 1274             array[a++] = array[b];
 1275             array[b] = temp;
 1276           }
 1277           b++;
 1278         }
 1279         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
 1280           if (comparison == 0) {
 1281             temp = array[c];
 1282             array[c] = array[d];
 1283             array[d--] = temp;
 1284           }
 1285           c--;
 1286         }
 1287         if (b > c) {
 1288           break;
 1289         }
 1290         temp = array[b];
 1291         array[b++] = array[c];
 1292         array[c--] = temp;
 1293       }
 1294       length = a - start < b - a ? a - start : b - a;
 1295       int l = start;
 1296       int h = b - length;
 1297       while (length-- > 0) {
 1298         temp = array[l];
 1299         array[l++] = array[h];
 1300         array[h++] = temp;
 1301       }
 1302       length = d - c < end - 1 - d ? d - c : end - 1 - d;
 1303       l = b;
 1304       h = end - length;
 1305       while (length-- > 0) {
 1306         temp = array[l];
 1307         array[l++] = array[h];
 1308         array[h++] = temp;
 1309       }
 1310       if ((length = b - a) > 0) {
 1311         quickSort0(start, start + length, array, comp);
 1312       }
 1313       if ((length = d - c) > 0) {
 1314         quickSort0(end - length, end, array, comp);
 1315       }
 1316     }
 1317     
 1318     /**
 1319      * Sorts the specified range in the array in a specified order.
 1320      * 
 1321      * @param array
 1322      *          the array to be sorted.
 1323      * @param start
 1324      *          the start index to sort.
 1325      * @param end
 1326      *          the last + 1 index to sort.
 1327      * @param comp
 1328      *          the comparator.
 1329      * @throws IllegalArgumentException
 1330      *           if {@code start > end}.
 1331      * @throws ArrayIndexOutOfBoundsException
 1332      *           if {@code start < 0} or {@code end > array.length}.
 1333      */
 1334     public static <T> void quickSort(T[] array, int start, int end,
 1335         Comparator<T> comp) {
 1336       if (array == null) {
 1337         throw new NullPointerException();
 1338       }
 1339       checkBounds(array.length, start, end);
 1340       quickSort0(start, end, array, comp);
 1341     }
 1342     
 1343     private static final class ComparableAdaptor<T extends Comparable<? super T>>
 1344         implements Comparator<T> {
 1345       
 1346       @Override
 1347       public int compare(T o1, T o2) {
 1348         return o1.compareTo(o2);
 1349       }
 1350       
 1351     }
 1352     
 1353     /**
 1354      * Sort the specified range of an array of object that implement the Comparable
 1355      * interface.
 1356      * @param <T> The type of object.
 1357      * @param array the array.
 1358      * @param start the first index.
 1359      * @param end the last index (exclusive).
 1360      */
 1361     public static <T extends Comparable<? super T>> void quickSort(T[] array,
 1362         int start, int end) {
 1363       quickSort(array, start, end, new ComparableAdaptor<T>());
 1364     }
 1365     
 1366     private static <T> void quickSort0(int start, int end, T[] array,
 1367         Comparator<T> comp) {
 1368       T temp;
 1369       int length = end - start;
 1370       if (length < 7) {
 1371         for (int i = start + 1; i < end; i++) {
 1372           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
 1373             temp = array[j];
 1374             array[j] = array[j - 1];
 1375             array[j - 1] = temp;
 1376           }
 1377         }
 1378         return;
 1379       }
 1380       int middle = (start + end) / 2;
 1381       if (length > 7) {
 1382         int bottom = start;
 1383         int top = end - 1;
 1384         if (length > 40) {
 1385           length /= 8;
 1386           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
 1387               comp);
 1388           middle = med3(array, middle - length, middle, middle + length, comp);
 1389           top = med3(array, top - (2 * length), top - length, top, comp);
 1390         }
 1391         middle = med3(array, bottom, middle, top, comp);
 1392       }
 1393       T partionValue = array[middle];
 1394       int a, b, c, d;
 1395       a = b = start;
 1396       c = d = end - 1;
 1397       while (true) {
 1398         int comparison;
 1399         while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
 1400           if (comparison == 0) {
 1401             temp = array[a];
 1402             array[a++] = array[b];
 1403             array[b] = temp;
 1404           }
 1405           b++;
 1406         }
 1407         while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
 1408           if (comparison == 0) {
 1409             temp = array[c];
 1410             array[c] = array[d];
 1411             array[d--] = temp;
 1412           }
 1413           c--;
 1414         }
 1415         if (b > c) {
 1416           break;
 1417         }
 1418         temp = array[b];
 1419         array[b++] = array[c];
 1420         array[c--] = temp;
 1421       }
 1422       length = a - start < b - a ? a - start : b - a;
 1423       int l = start;
 1424       int h = b - length;
 1425       while (length-- > 0) {
 1426         temp = array[l];
 1427         array[l++] = array[h];
 1428         array[h++] = temp;
 1429       }
 1430       length = d - c < end - 1 - d ? d - c : end - 1 - d;
 1431       l = b;
 1432       h = end - length;
 1433       while (length-- > 0) {
 1434         temp = array[l];
 1435         array[l++] = array[h];
 1436         array[h++] = temp;
 1437       }
 1438       if ((length = b - a) > 0) {
 1439         quickSort0(start, start + length, array, comp);
 1440       }
 1441       if ((length = d - c) > 0) {
 1442         quickSort0(end - length, end, array, comp);
 1443       }
 1444     }
 1445     
 1446     /**
 1447      * Sorts the specified range in the array in ascending numerical order.
 1448      * 
 1449      * @param array
 1450      *          the {@code short} array to be sorted.
 1451      * @param start
 1452      *          the start index to sort.
 1453      * @param end
 1454      *          the last + 1 index to sort.
 1455      * @throws IllegalArgumentException
 1456      *           if {@code start > end}.
 1457      * @throws ArrayIndexOutOfBoundsException
 1458      *           if {@code start < 0} or {@code end > array.length}.
 1459      */
 1460     public static void quickSort(short[] array, int start, int end,
 1461         ShortComparator comp) {
 1462       if (array == null) {
 1463         throw new NullPointerException();
 1464       }
 1465       checkBounds(array.length, start, end);
 1466       quickSort0(start, end, array, comp);
 1467     }
 1468     
 1469     private static void quickSort0(int start, int end, short[] array,
 1470         ShortComparator comp) {
 1471       short temp;
 1472       int length = end - start;
 1473       if (length < 7) {
 1474         for (int i = start + 1; i < end; i++) {
 1475           for (int j = i; j > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
 1476             temp = array[j];
 1477             array[j] = array[j - 1];
 1478             array[j - 1] = temp;
 1479           }
 1480         }
 1481         return;
 1482       }
 1483       int middle = (start + end) / 2;
 1484       if (length > 7) {
 1485         int bottom = start;
 1486         int top = end - 1;
 1487         if (length > 40) {
 1488           length /= 8;
 1489           bottom = med3(array, bottom, bottom + length, bottom + (2 * length),
 1490               comp);
 1491           middle = med3(array, middle - length, middle, middle + length, comp);
 1492           top = med3(array, top - (2 * length), top - length, top, comp);
 1493         }
 1494         middle = med3(array, bottom, middle, top, comp);
 1495       }
 1496       short partionValue = array[middle];
 1497       int a, b, c, d;
 1498       a = b = start;
 1499       c = d = end - 1;
 1500       while (true) {
 1501         int comparison;
 1502         while (b <= c && (comparison = comp.compare(array[b], partionValue)) < 0) {
 1503           if (comparison == 0) {
 1504             temp = array[a];
 1505             array[a++] = array[b];
 1506             array[b] = temp;
 1507           }
 1508           b++;
 1509         }
 1510         while (c >= b && (comparison = comp.compare(array[c], partionValue)) > 0) {
 1511           if (comparison == 0) {
 1512             temp = array[c];
 1513             array[c] = array[d];
 1514             array[d--] = temp;
 1515           }
 1516           c--;
 1517         }
 1518         if (b > c) {
 1519           break;
 1520         }
 1521         temp = array[b];
 1522         array[b++] = array[c];
 1523         array[c--] = temp;
 1524       }
 1525       length = a - start < b - a ? a - start : b - a;
 1526       int l = start;
 1527       int h = b - length;
 1528       while (length-- > 0) {
 1529         temp = array[l];
 1530         array[l++] = array[h];
 1531         array[h++] = temp;
 1532       }
 1533       length = d - c < end - 1 - d ? d - c : end - 1 - d;
 1534       l = b;
 1535       h = end - length;
 1536       while (length-- > 0) {
 1537         temp = array[l];
 1538         array[l++] = array[h];
 1539         array[h++] = temp;
 1540       }
 1541       if ((length = b - a) > 0) {
 1542         quickSort0(start, start + length, array, comp);
 1543       }
 1544       if ((length = d - c) > 0) {
 1545         quickSort0(end - length, end, array, comp);
 1546       }
 1547     }
 1548   
 1549     /**
 1550      * Perform a merge sort on the specified range of an array.
 1551      * 
 1552      * @param <T> the type of object in the array.
 1553      * @param array the array.
 1554      * @param start first index. 
 1555      * @param end last index (exclusive).
 1556      * @param comp comparator object.
 1557      */
 1558     @SuppressWarnings("unchecked") // required to make the temp array work, afaict.
 1559     public static <T> void mergeSort(T[] array, int start, int end,
 1560         Comparator<T> comp) {
 1561       checkBounds(array.length, start, end);
 1562       int length = end - start;
 1563       if (length <= 0) {
 1564         return;
 1565       }
 1566       
 1567       T[] out = (T[]) new Object[array.length];
 1568       System.arraycopy(array, start, out, start, length);
 1569       mergeSort(out, array, start, end, comp);
 1570     }
 1571     
 1572     /**
 1573      * Perform a merge sort of the specific range of an array of objects that implement
 1574      * Comparable.
 1575      * @param <T> the type of the objects in the array.
 1576      * @param array the array.
 1577      * @param start the first index.
 1578      * @param end the last index (exclusive).
 1579      */
 1580     public static <T extends Comparable<? super T>> void mergeSort(T[] array, int start, int end) {
 1581       mergeSort(array, start, end, new ComparableAdaptor<T>());
 1582     }
 1583     
 1584     /**
 1585      * Performs a sort on the section of the array between the given indices using
 1586      * a mergesort with exponential search algorithm (in which the merge is
 1587      * performed by exponential search). n*log(n) performance is guaranteed and in
 1588      * the average case it will be faster then any mergesort in which the merge is
 1589      * performed by linear search.
 1590      * 
 1591      * @param in
 1592      *          - the array for sorting.
 1593      * @param out
 1594      *          - the result, sorted array.
 1595      * @param start
 1596      *          the start index
 1597      * @param end
 1598      *          the end index + 1
 1599      * @param c
 1600      *          - the comparator to determine the order of the array.
 1601      */
 1602     private static <T> void mergeSort(T[] in, T[] out, int start, int end,
 1603         Comparator<T> c) {
 1604       int len = end - start;
 1605       // use insertion sort for small arrays
 1606       if (len <= SIMPLE_LENGTH) {
 1607         for (int i = start + 1; i < end; i++) {
 1608           T current = out[i];
 1609           T prev = out[i - 1];
 1610           if (c.compare(prev, current) > 0) {
 1611             int j = i;
 1612             do {
 1613               out[j--] = prev;
 1614             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 1615             out[j] = current;
 1616           }
 1617         }
 1618         return;
 1619       }
 1620       int med = (end + start) >>> 1;
 1621       mergeSort(out, in, start, med, c);
 1622       mergeSort(out, in, med, end, c);
 1623       
 1624       // merging
 1625       
 1626       // if arrays are already sorted - no merge
 1627       if (c.compare(in[med - 1], in[med]) <= 0) {
 1628         System.arraycopy(in, start, out, start, len);
 1629         return;
 1630       }
 1631       int r = med, i = start;
 1632       
 1633       // use merging with exponential search
 1634       do {
 1635         T fromVal = in[start];
 1636         T rVal = in[r];
 1637         if (c.compare(fromVal, rVal) <= 0) {
 1638           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 1639           int toCopy = l_1 - start + 1;
 1640           System.arraycopy(in, start, out, i, toCopy);
 1641           i += toCopy;
 1642           out[i++] = rVal;
 1643           r++;
 1644           start = l_1 + 1;
 1645         } else {
 1646           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 1647           int toCopy = r_1 - r + 1;
 1648           System.arraycopy(in, r, out, i, toCopy);
 1649           i += toCopy;
 1650           out[i++] = fromVal;
 1651           start++;
 1652           r = r_1 + 1;
 1653         }
 1654       } while ((end - r) > 0 && (med - start) > 0);
 1655       
 1656       // copy rest of array
 1657       if ((end - r) <= 0) {
 1658         System.arraycopy(in, start, out, i, med - start);
 1659       } else {
 1660         System.arraycopy(in, r, out, i, end - r);
 1661       }
 1662     }
 1663     
 1664     /**
 1665      * Finds the place of specified range of specified sorted array, where the
 1666      * element should be inserted for getting sorted array. Uses exponential
 1667      * search algorithm.
 1668      * 
 1669      * @param arr
 1670      *          - the array with already sorted range
 1671      * @param val
 1672      *          - object to be inserted
 1673      * @param l
 1674      *          - the start index
 1675      * @param r
 1676      *          - the end index
 1677      * @param bnd
 1678      *          - possible values 0,-1. "-1" - val is located at index more then
 1679      *          elements equals to val. "0" - val is located at index less then
 1680      *          elements equals to val.
 1681      * @param c
 1682      *          - the comparator used to compare Objects
 1683      */
 1684     private static <T> int find(T[] arr, T val, int bnd, int l, int r,
 1685         Comparator<T> c) {
 1686       int m = l;
 1687       int d = 1;
 1688       while (m <= r) {
 1689         if (c.compare(val, arr[m]) > bnd) {
 1690           l = m + 1;
 1691         } else {
 1692           r = m - 1;
 1693           break;
 1694         }
 1695         m += d;
 1696         d <<= 1;
 1697       }
 1698       while (l <= r) {
 1699         m = (l + r) >>> 1;
 1700         if (c.compare(val, arr[m]) > bnd) {
 1701           l = m + 1;
 1702         } else {
 1703           r = m - 1;
 1704         }
 1705       }
 1706       return l - 1;
 1707     }
 1708     
 1709     private static final ByteComparator naturalByteComparison = new ByteComparator() {
 1710       @Override
 1711       public int compare(byte o1, byte o2) {
 1712         return o1 - o2;
 1713       }};
 1714       
 1715       /**
 1716        * Perform a merge sort on a range of a byte array, using numerical order.
 1717        * @param array the array.
 1718        * @param start the first index.
 1719        * @param end the last index (exclusive).
 1720        */
 1721     public static void mergeSort(byte[] array, int start, int end) {
 1722       mergeSort(array, start, end, naturalByteComparison);
 1723     }
 1724     
 1725     /**
 1726      * Perform a merge sort on a range of a byte array using a specified ordering.
 1727      * @param array the array.
 1728      * @param start the first index.
 1729      * @param end the last index (exclusive).
 1730      * @param comp the comparator object.
 1731      */
 1732     public static void mergeSort(byte[] array, int start, int end, ByteComparator comp) {
 1733       checkBounds(array.length, start, end);
 1734       byte[] out = Arrays.copyOf(array, array.length);
 1735       mergeSort(out, array, start, end, comp);
 1736     }
 1737   
 1738     private static void mergeSort(byte[] in, byte[] out, int start, int end,
 1739         ByteComparator c) {
 1740       int len = end - start;
 1741       // use insertion sort for small arrays
 1742       if (len <= SIMPLE_LENGTH) {
 1743         for (int i = start + 1; i < end; i++) {
 1744           byte current = out[i];
 1745           byte prev = out[i - 1];
 1746           if (c.compare(prev, current) > 0) {
 1747             int j = i;
 1748             do {
 1749               out[j--] = prev;
 1750             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 1751             out[j] = current;
 1752           }
 1753         }
 1754         return;
 1755       }
 1756       int med = (end + start) >>> 1;
 1757       mergeSort(out, in, start, med, c);
 1758       mergeSort(out, in, med, end, c);
 1759       
 1760       // merging
 1761       
 1762       // if arrays are already sorted - no merge
 1763       if (c.compare(in[med - 1], in[med]) <= 0) {
 1764         System.arraycopy(in, start, out, start, len);
 1765         return;
 1766       }
 1767       int r = med, i = start;
 1768       
 1769       // use merging with exponential search
 1770       do {
 1771         byte fromVal = in[start];
 1772         byte rVal = in[r];
 1773         if (c.compare(fromVal, rVal) <= 0) {
 1774           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 1775           int toCopy = l_1 - start + 1;
 1776           System.arraycopy(in, start, out, i, toCopy);
 1777           i += toCopy;
 1778           out[i++] = rVal;
 1779           r++;
 1780           start = l_1 + 1;
 1781         } else {
 1782           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 1783           int toCopy = r_1 - r + 1;
 1784           System.arraycopy(in, r, out, i, toCopy);
 1785           i += toCopy;
 1786           out[i++] = fromVal;
 1787           start++;
 1788           r = r_1 + 1;
 1789         }
 1790       } while ((end - r) > 0 && (med - start) > 0);
 1791       
 1792       // copy rest of array
 1793       if ((end - r) <= 0) {
 1794         System.arraycopy(in, start, out, i, med - start);
 1795       } else {
 1796         System.arraycopy(in, r, out, i, end - r);
 1797       }
 1798     }
 1799   
 1800     private static int find(byte[] arr, byte val, int bnd, int l, int r,
 1801         ByteComparator c) {
 1802       int m = l;
 1803       int d = 1;
 1804       while (m <= r) {
 1805         if (c.compare(val, arr[m]) > bnd) {
 1806           l = m + 1;
 1807         } else {
 1808           r = m - 1;
 1809           break;
 1810         }
 1811         m += d;
 1812         d <<= 1;
 1813       }
 1814       while (l <= r) {
 1815         m = (l + r) >>> 1;
 1816         if (c.compare(val, arr[m]) > bnd) {
 1817           l = m + 1;
 1818         } else {
 1819           r = m - 1;
 1820         }
 1821       }
 1822       return l - 1;
 1823     }
 1824     
 1825     private static final CharComparator naturalCharComparison = new CharComparator() {
 1826       @Override
 1827       public int compare(char o1, char o2) {
 1828         return o1 - o2;
 1829       }};
 1830       
 1831       /**
 1832        * Perform a merge sort on a range of a char array, using numerical order.
 1833        * @param array the array.
 1834        * @param start the first index.
 1835        * @param end the last index (exclusive).
 1836        */
 1837     public static void mergeSort(char[] array, int start, int end) {
 1838       mergeSort(array, start, end, naturalCharComparison);
 1839     }
 1840   
 1841     /**
 1842      * Perform a merge sort on a range of a char array using a specified ordering.
 1843      * @param array the array.
 1844      * @param start the first index.
 1845      * @param end the last index (exclusive).
 1846      * @param comp the comparator object.
 1847      */
 1848     public static void mergeSort(char[] array, int start, int end, CharComparator comp) {
 1849       checkBounds(array.length, start, end);
 1850       char[] out = Arrays.copyOf(array, array.length);
 1851       mergeSort(out, array, start, end, comp);
 1852     }
 1853   
 1854     private static void mergeSort(char[] in, char[] out, int start, int end,
 1855         CharComparator c) {
 1856       int len = end - start;
 1857       // use insertion sort for small arrays
 1858       if (len <= SIMPLE_LENGTH) {
 1859         for (int i = start + 1; i < end; i++) {
 1860           char current = out[i];
 1861           char prev = out[i - 1];
 1862           if (c.compare(prev, current) > 0) {
 1863             int j = i;
 1864             do {
 1865               out[j--] = prev;
 1866             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 1867             out[j] = current;
 1868           }
 1869         }
 1870         return;
 1871       }
 1872       int med = (end + start) >>> 1;
 1873       mergeSort(out, in, start, med, c);
 1874       mergeSort(out, in, med, end, c);
 1875       
 1876       // merging
 1877       
 1878       // if arrays are already sorted - no merge
 1879       if (c.compare(in[med - 1], in[med]) <= 0) {
 1880         System.arraycopy(in, start, out, start, len);
 1881         return;
 1882       }
 1883       int r = med, i = start;
 1884       
 1885       // use merging with exponential search
 1886       do {
 1887         char fromVal = in[start];
 1888         char rVal = in[r];
 1889         if (c.compare(fromVal, rVal) <= 0) {
 1890           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 1891           int toCopy = l_1 - start + 1;
 1892           System.arraycopy(in, start, out, i, toCopy);
 1893           i += toCopy;
 1894           out[i++] = rVal;
 1895           r++;
 1896           start = l_1 + 1;
 1897         } else {
 1898           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 1899           int toCopy = r_1 - r + 1;
 1900           System.arraycopy(in, r, out, i, toCopy);
 1901           i += toCopy;
 1902           out[i++] = fromVal;
 1903           start++;
 1904           r = r_1 + 1;
 1905         }
 1906       } while ((end - r) > 0 && (med - start) > 0);
 1907       
 1908       // copy rest of array
 1909       if ((end - r) <= 0) {
 1910         System.arraycopy(in, start, out, i, med - start);
 1911       } else {
 1912         System.arraycopy(in, r, out, i, end - r);
 1913       }
 1914     }
 1915   
 1916     private static int find(char[] arr, char val, int bnd, int l, int r,
 1917         CharComparator c) {
 1918       int m = l;
 1919       int d = 1;
 1920       while (m <= r) {
 1921         if (c.compare(val, arr[m]) > bnd) {
 1922           l = m + 1;
 1923         } else {
 1924           r = m - 1;
 1925           break;
 1926         }
 1927         m += d;
 1928         d <<= 1;
 1929       }
 1930       while (l <= r) {
 1931         m = (l + r) >>> 1;
 1932         if (c.compare(val, arr[m]) > bnd) {
 1933           l = m + 1;
 1934         } else {
 1935           r = m - 1;
 1936         }
 1937       }
 1938       return l - 1;
 1939     }
 1940     
 1941     private static final ShortComparator naturalShortComparison = new ShortComparator() {
 1942       @Override
 1943       public int compare(short o1, short o2) {
 1944         return o1 - o2;
 1945       }};
 1946       
 1947       /**
 1948        * Perform a merge sort on a range of a short array, using numerical order.
 1949        * @param array the array.
 1950        * @param start the first index.
 1951        * @param end the last index (exclusive).
 1952        */
 1953     public static void mergeSort(short[] array, int start, int end) {
 1954       mergeSort(array, start, end, naturalShortComparison);
 1955     }
 1956     
 1957     public static void mergeSort(short[] array, int start, int end, ShortComparator comp) {
 1958       checkBounds(array.length, start, end);
 1959       short[] out = Arrays.copyOf(array, array.length);
 1960       mergeSort(out, array, start, end, comp);
 1961     }
 1962   
 1963     
 1964     /**
 1965      * Perform a merge sort on a range of a short array using a specified ordering.
 1966      * @param in the array.
 1967      * @param start the first index.
 1968      * @param end the last index (exclusive).
 1969      * @param c the comparator object.
 1970      */
 1971     private static void mergeSort(short[] in, short[] out, int start, int end,
 1972         ShortComparator c) {
 1973       int len = end - start;
 1974       // use insertion sort for small arrays
 1975       if (len <= SIMPLE_LENGTH) {
 1976         for (int i = start + 1; i < end; i++) {
 1977           short current = out[i];
 1978           short prev = out[i - 1];
 1979           if (c.compare(prev, current) > 0) {
 1980             int j = i;
 1981             do {
 1982               out[j--] = prev;
 1983             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 1984             out[j] = current;
 1985           }
 1986         }
 1987         return;
 1988       }
 1989       int med = (end + start) >>> 1;
 1990       mergeSort(out, in, start, med, c);
 1991       mergeSort(out, in, med, end, c);
 1992       
 1993       // merging
 1994       
 1995       // if arrays are already sorted - no merge
 1996       if (c.compare(in[med - 1], in[med]) <= 0) {
 1997         System.arraycopy(in, start, out, start, len);
 1998         return;
 1999       }
 2000       int r = med, i = start;
 2001       
 2002       // use merging with exponential search
 2003       do {
 2004         short fromVal = in[start];
 2005         short rVal = in[r];
 2006         if (c.compare(fromVal, rVal) <= 0) {
 2007           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 2008           int toCopy = l_1 - start + 1;
 2009           System.arraycopy(in, start, out, i, toCopy);
 2010           i += toCopy;
 2011           out[i++] = rVal;
 2012           r++;
 2013           start = l_1 + 1;
 2014         } else {
 2015           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 2016           int toCopy = r_1 - r + 1;
 2017           System.arraycopy(in, r, out, i, toCopy);
 2018           i += toCopy;
 2019           out[i++] = fromVal;
 2020           start++;
 2021           r = r_1 + 1;
 2022         }
 2023       } while ((end - r) > 0 && (med - start) > 0);
 2024       
 2025       // copy rest of array
 2026       if ((end - r) <= 0) {
 2027         System.arraycopy(in, start, out, i, med - start);
 2028       } else {
 2029         System.arraycopy(in, r, out, i, end - r);
 2030       }
 2031     }
 2032   
 2033     private static int find(short[] arr, short val, int bnd, int l, int r,
 2034         ShortComparator c) {
 2035       int m = l;
 2036       int d = 1;
 2037       while (m <= r) {
 2038         if (c.compare(val, arr[m]) > bnd) {
 2039           l = m + 1;
 2040         } else {
 2041           r = m - 1;
 2042           break;
 2043         }
 2044         m += d;
 2045         d <<= 1;
 2046       }
 2047       while (l <= r) {
 2048         m = (l + r) >>> 1;
 2049         if (c.compare(val, arr[m]) > bnd) {
 2050           l = m + 1;
 2051         } else {
 2052           r = m - 1;
 2053         }
 2054       }
 2055       return l - 1;
 2056     }
 2057     
 2058     private static final IntComparator naturalIntComparison = new IntComparator() {
 2059       @Override
 2060       public int compare(int o1, int o2) {
 2061         return o1 < o2 ? -1 : o1 > o2 ? 1 : 0;
 2062       }};
 2063       
 2064     public static void mergeSort(int[] array, int start, int end) {
 2065       mergeSort(array, start, end, naturalIntComparison);
 2066     }
 2067   
 2068     /**
 2069      * Perform a merge sort on a range of a int array using numerical order.
 2070      * @param array the array.
 2071      * @param start the first index.
 2072      * @param end the last index (exclusive).
 2073      * @param comp the comparator object.
 2074      */
 2075     public static void mergeSort(int[] array, int start, int end, IntComparator comp) {
 2076       checkBounds(array.length, start, end);
 2077       int[] out = Arrays.copyOf(array, array.length);
 2078       mergeSort(out, array, start, end, comp);
 2079     }
 2080   
 2081     /**
 2082      * Perform a merge sort on a range of a int array using a specified ordering.
 2083      * @param in the array.
 2084      * @param start the first index.
 2085      * @param end the last index (exclusive).
 2086      * @param c the comparator object.
 2087      */
 2088     private static void mergeSort(int[] in, int[] out, int start, int end,
 2089         IntComparator c) {
 2090       int len = end - start;
 2091       // use insertion sort for small arrays
 2092       if (len <= SIMPLE_LENGTH) {
 2093         for (int i = start + 1; i < end; i++) {
 2094           int current = out[i];
 2095           int prev = out[i - 1];
 2096           if (c.compare(prev, current) > 0) {
 2097             int j = i;
 2098             do {
 2099               out[j--] = prev;
 2100             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 2101             out[j] = current;
 2102           }
 2103         }
 2104         return;
 2105       }
 2106       int med = (end + start) >>> 1;
 2107       mergeSort(out, in, start, med, c);
 2108       mergeSort(out, in, med, end, c);
 2109       
 2110       // merging
 2111       
 2112       // if arrays are already sorted - no merge
 2113       if (c.compare(in[med - 1], in[med]) <= 0) {
 2114         System.arraycopy(in, start, out, start, len);
 2115         return;
 2116       }
 2117       int r = med, i = start;
 2118       
 2119       // use merging with exponential search
 2120       do {
 2121         int fromVal = in[start];
 2122         int rVal = in[r];
 2123         if (c.compare(fromVal, rVal) <= 0) {
 2124           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 2125           int toCopy = l_1 - start + 1;
 2126           System.arraycopy(in, start, out, i, toCopy);
 2127           i += toCopy;
 2128           out[i++] = rVal;
 2129           r++;
 2130           start = l_1 + 1;
 2131         } else {
 2132           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 2133           int toCopy = r_1 - r + 1;
 2134           System.arraycopy(in, r, out, i, toCopy);
 2135           i += toCopy;
 2136           out[i++] = fromVal;
 2137           start++;
 2138           r = r_1 + 1;
 2139         }
 2140       } while ((end - r) > 0 && (med - start) > 0);
 2141       
 2142       // copy rest of array
 2143       if ((end - r) <= 0) {
 2144         System.arraycopy(in, start, out, i, med - start);
 2145       } else {
 2146         System.arraycopy(in, r, out, i, end - r);
 2147       }
 2148     }
 2149   
 2150     private static int find(int[] arr, int val, int bnd, int l, int r,
 2151         IntComparator c) {
 2152       int m = l;
 2153       int d = 1;
 2154       while (m <= r) {
 2155         if (c.compare(val, arr[m]) > bnd) {
 2156           l = m + 1;
 2157         } else {
 2158           r = m - 1;
 2159           break;
 2160         }
 2161         m += d;
 2162         d <<= 1;
 2163       }
 2164       while (l <= r) {
 2165         m = (l + r) >>> 1;
 2166         if (c.compare(val, arr[m]) > bnd) {
 2167           l = m + 1;
 2168         } else {
 2169           r = m - 1;
 2170         }
 2171       }
 2172       return l - 1;
 2173     }
 2174     
 2175     
 2176     private static final LongComparator naturalLongComparison = new LongComparator() {
 2177       @Override
 2178       public int compare(long o1, long o2) {
 2179         return o1 < o2 ? -1 : o1 > o2 ? 1 : 0;
 2180       }};
 2181       
 2182       /**
 2183        * Perform a merge sort on a range of a long array using numerical order.
 2184        * @param array the array.
 2185        * @param start the first index.
 2186        * @param end the last index (exclusive).
 2187        */
 2188     public static void mergeSort(long[] array, int start, int end) {
 2189       mergeSort(array, start, end, naturalLongComparison);
 2190     }
 2191   
 2192     /**
 2193      * Perform a merge sort on a range of a long array using a specified ordering.
 2194      * @param array the array.
 2195      * @param start the first index.
 2196      * @param end the last index (exclusive).
 2197      * @param comp the comparator object.
 2198      */
 2199     public static void mergeSort(long[] array, int start, int end, LongComparator comp) {
 2200       checkBounds(array.length, start, end);
 2201       long[] out = Arrays.copyOf(array, array.length);
 2202       mergeSort(out, array, start, end, comp);
 2203     }
 2204   
 2205     private static void mergeSort(long[] in, long[] out, int start, int end,
 2206         LongComparator c) {
 2207       int len = end - start;
 2208       // use insertion sort for small arrays
 2209       if (len <= SIMPLE_LENGTH) {
 2210         for (int i = start + 1; i < end; i++) {
 2211           long current = out[i];
 2212           long prev = out[i - 1];
 2213           if (c.compare(prev, current) > 0) {
 2214             int j = i;
 2215             do {
 2216               out[j--] = prev;
 2217             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 2218             out[j] = current;
 2219           }
 2220         }
 2221         return;
 2222       }
 2223       int med = (end + start) >>> 1;
 2224       mergeSort(out, in, start, med, c);
 2225       mergeSort(out, in, med, end, c);
 2226       
 2227       // merging
 2228       
 2229       // if arrays are already sorted - no merge
 2230       if (c.compare(in[med - 1], in[med]) <= 0) {
 2231         System.arraycopy(in, start, out, start, len);
 2232         return;
 2233       }
 2234       int r = med, i = start;
 2235       
 2236       // use merging with exponential search
 2237       do {
 2238         long fromVal = in[start];
 2239         long rVal = in[r];
 2240         if (c.compare(fromVal, rVal) <= 0) {
 2241           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 2242           int toCopy = l_1 - start + 1;
 2243           System.arraycopy(in, start, out, i, toCopy);
 2244           i += toCopy;
 2245           out[i++] = rVal;
 2246           r++;
 2247           start = l_1 + 1;
 2248         } else {
 2249           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 2250           int toCopy = r_1 - r + 1;
 2251           System.arraycopy(in, r, out, i, toCopy);
 2252           i += toCopy;
 2253           out[i++] = fromVal;
 2254           start++;
 2255           r = r_1 + 1;
 2256         }
 2257       } while ((end - r) > 0 && (med - start) > 0);
 2258       
 2259       // copy rest of array
 2260       if ((end - r) <= 0) {
 2261         System.arraycopy(in, start, out, i, med - start);
 2262       } else {
 2263         System.arraycopy(in, r, out, i, end - r);
 2264       }
 2265     }
 2266   
 2267     private static int find(long[] arr, long val, int bnd, int l, int r,
 2268         LongComparator c) {
 2269       int m = l;
 2270       int d = 1;
 2271       while (m <= r) {
 2272         if (c.compare(val, arr[m]) > bnd) {
 2273           l = m + 1;
 2274         } else {
 2275           r = m - 1;
 2276           break;
 2277         }
 2278         m += d;
 2279         d <<= 1;
 2280       }
 2281       while (l <= r) {
 2282         m = (l + r) >>> 1;
 2283         if (c.compare(val, arr[m]) > bnd) {
 2284           l = m + 1;
 2285         } else {
 2286           r = m - 1;
 2287         }
 2288       }
 2289       return l - 1;
 2290     }
 2291     
 2292     private static final FloatComparator naturalFloatComparison = new FloatComparator() {
 2293       @Override
 2294       public int compare(float o1, float o2) {
 2295         return Float.compare(o1, o2);
 2296       }};
 2297       
 2298       /**
 2299        * Perform a merge sort on a range of a float array using Float.compare for an ordering.
 2300        * @param array the array.
 2301        * @param start the first index.
 2302        * @param end the last index (exclusive).
 2303        */
 2304     public static void mergeSort(float[] array, int start, int end) {
 2305       mergeSort(array, start, end, naturalFloatComparison);
 2306     }
 2307   
 2308     /**
 2309      * Perform a merge sort on a range of a float array using a specified ordering.
 2310      * @param array the array.
 2311      * @param start the first index.
 2312      * @param end the last index (exclusive).
 2313      * @param comp the comparator object.
 2314      */
 2315     public static void mergeSort(float[] array, int start, int end, FloatComparator comp) {
 2316       checkBounds(array.length, start, end);
 2317       float[] out = Arrays.copyOf(array, array.length);
 2318       mergeSort(out, array, start, end, comp);
 2319     }
 2320   
 2321     private static void mergeSort(float[] in, float[] out, int start, int end,
 2322         FloatComparator c) {
 2323       int len = end - start;
 2324       // use insertion sort for small arrays
 2325       if (len <= SIMPLE_LENGTH) {
 2326         for (int i = start + 1; i < end; i++) {
 2327           float current = out[i];
 2328           float prev = out[i - 1];
 2329           if (c.compare(prev, current) > 0) {
 2330             int j = i;
 2331             do {
 2332               out[j--] = prev;
 2333             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 2334             out[j] = current;
 2335           }
 2336         }
 2337         return;
 2338       }
 2339       int med = (end + start) >>> 1;
 2340       mergeSort(out, in, start, med, c);
 2341       mergeSort(out, in, med, end, c);
 2342       
 2343       // merging
 2344       
 2345       // if arrays are already sorted - no merge
 2346       if (c.compare(in[med - 1], in[med]) <= 0) {
 2347         System.arraycopy(in, start, out, start, len);
 2348         return;
 2349       }
 2350       int r = med, i = start;
 2351       
 2352       // use merging with exponential search
 2353       do {
 2354         float fromVal = in[start];
 2355         float rVal = in[r];
 2356         if (c.compare(fromVal, rVal) <= 0) {
 2357           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 2358           int toCopy = l_1 - start + 1;
 2359           System.arraycopy(in, start, out, i, toCopy);
 2360           i += toCopy;
 2361           out[i++] = rVal;
 2362           r++;
 2363           start = l_1 + 1;
 2364         } else {
 2365           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 2366           int toCopy = r_1 - r + 1;
 2367           System.arraycopy(in, r, out, i, toCopy);
 2368           i += toCopy;
 2369           out[i++] = fromVal;
 2370           start++;
 2371           r = r_1 + 1;
 2372         }
 2373       } while ((end - r) > 0 && (med - start) > 0);
 2374       
 2375       // copy rest of array
 2376       if ((end - r) <= 0) {
 2377         System.arraycopy(in, start, out, i, med - start);
 2378       } else {
 2379         System.arraycopy(in, r, out, i, end - r);
 2380       }
 2381     }
 2382   
 2383     private static int find(float[] arr, float val, int bnd, int l, int r,
 2384         FloatComparator c) {
 2385       int m = l;
 2386       int d = 1;
 2387       while (m <= r) {
 2388         if (c.compare(val, arr[m]) > bnd) {
 2389           l = m + 1;
 2390         } else {
 2391           r = m - 1;
 2392           break;
 2393         }
 2394         m += d;
 2395         d <<= 1;
 2396       }
 2397       while (l <= r) {
 2398         m = (l + r) >>> 1;
 2399         if (c.compare(val, arr[m]) > bnd) {
 2400           l = m + 1;
 2401         } else {
 2402           r = m - 1;
 2403         }
 2404       }
 2405       return l - 1;
 2406     }
 2407     
 2408     private static final DoubleComparator naturalDoubleComparison = new DoubleComparator() {
 2409       @Override
 2410       public int compare(double o1, double o2) {
 2411         return Double.compare(o1, o2);
 2412       }};
 2413       
 2414       
 2415       /**
 2416        * Perform a merge sort on a range of a double array using a Double.compare as an ordering.
 2417        * @param array the array.
 2418        * @param start the first index.
 2419        * @param end the last index (exclusive).
 2420        */
 2421     public static void mergeSort(double[] array, int start, int end) {
 2422       mergeSort(array, start, end, naturalDoubleComparison);
 2423     }
 2424   
 2425     /**
 2426      * Perform a merge sort on a range of a double array using a specified ordering.
 2427      * @param array the array.
 2428      * @param start the first index.
 2429      * @param end the last index (exclusive).
 2430      * @param comp the comparator object.
 2431      */
 2432     public static void mergeSort(double[] array, int start, int end, DoubleComparator comp) {
 2433       checkBounds(array.length, start, end);
 2434       double[] out = Arrays.copyOf(array, array.length);
 2435       mergeSort(out, array, start, end, comp);
 2436     }
 2437   
 2438     private static void mergeSort(double[] in, double[] out, int start, int end,
 2439         DoubleComparator c) {
 2440       int len = end - start;
 2441       // use insertion sort for small arrays
 2442       if (len <= SIMPLE_LENGTH) {
 2443         for (int i = start + 1; i < end; i++) {
 2444           double current = out[i];
 2445           double prev = out[i - 1];
 2446           if (c.compare(prev, current) > 0) {
 2447             int j = i;
 2448             do {
 2449               out[j--] = prev;
 2450             } while (j > start && (c.compare(prev = out[j - 1], current) > 0));
 2451             out[j] = current;
 2452           }
 2453         }
 2454         return;
 2455       }
 2456       int med = (end + start) >>> 1;
 2457       mergeSort(out, in, start, med, c);
 2458       mergeSort(out, in, med, end, c);
 2459       
 2460       // merging
 2461       
 2462       // if arrays are already sorted - no merge
 2463       if (c.compare(in[med - 1], in[med]) <= 0) {
 2464         System.arraycopy(in, start, out, start, len);
 2465         return;
 2466       }
 2467       int r = med, i = start;
 2468       
 2469       // use merging with exponential search
 2470       do {
 2471         double fromVal = in[start];
 2472         double rVal = in[r];
 2473         if (c.compare(fromVal, rVal) <= 0) {
 2474           int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
 2475           int toCopy = l_1 - start + 1;
 2476           System.arraycopy(in, start, out, i, toCopy);
 2477           i += toCopy;
 2478           out[i++] = rVal;
 2479           r++;
 2480           start = l_1 + 1;
 2481         } else {
 2482           int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
 2483           int toCopy = r_1 - r + 1;
 2484           System.arraycopy(in, r, out, i, toCopy);
 2485           i += toCopy;
 2486           out[i++] = fromVal;
 2487           start++;
 2488           r = r_1 + 1;
 2489         }
 2490       } while ((end - r) > 0 && (med - start) > 0);
 2491       
 2492       // copy rest of array
 2493       if ((end - r) <= 0) {
 2494         System.arraycopy(in, start, out, i, med - start);
 2495       } else {
 2496         System.arraycopy(in, r, out, i, end - r);
 2497       }
 2498     }
 2499   
 2500     private static int find(double[] arr, double val, int bnd, int l, int r,
 2501         DoubleComparator c) {
 2502       int m = l;
 2503       int d = 1;
 2504       while (m <= r) {
 2505         if (c.compare(val, arr[m]) > bnd) {
 2506           l = m + 1;
 2507         } else {
 2508           r = m - 1;
 2509           break;
 2510         }
 2511         m += d;
 2512         d <<= 1;
 2513       }
 2514       while (l <= r) {
 2515         m = (l + r) >>> 1;
 2516         if (c.compare(val, arr[m]) > bnd) {
 2517           l = m + 1;
 2518         } else {
 2519           r = m - 1;
 2520         }
 2521       }
 2522       return l - 1;
 2523     }
 2524   
 2525     /**
 2526      * Transforms two consecutive sorted ranges into a single sorted range.  The initial ranges are <code>[first,
 2527      * middle)</code> and <code>[middle, last)</code>, and the resulting range is <code>[first, last)</code>. Elements in
 2528      * the first input range will precede equal elements in the second.
 2529      */
 2530     static void inplace_merge(int first, int middle, int last, IntComparator comp, Swapper swapper) {
 2531       if (first >= middle || middle >= last) {
 2532         return;
 2533       }
 2534       if (last - first == 2) {
 2535         if (comp.compare(middle, first) < 0) {
 2536           swapper.swap(first, middle);
 2537         }
 2538         return;
 2539       }
 2540       int firstCut;
 2541       int secondCut;
 2542       if (middle - first > last - middle) {
 2543         firstCut = first + (middle - first) / 2;
 2544         secondCut = lower_bound(middle, last, firstCut, comp);
 2545       } else {
 2546         secondCut = middle + (last - middle) / 2;
 2547         firstCut = upper_bound(first, middle, secondCut, comp);
 2548       }
 2549     
 2550       // rotate(firstCut, middle, secondCut, swapper);
 2551       // is manually inlined for speed (jitter inlining seems to work only for small call depths, even if methods are "static private")
 2552       // speedup = 1.7
 2553       // begin inline
 2554       int first2 = firstCut;
 2555       int middle2 = middle;
 2556       int last2 = secondCut;
 2557       if (middle2 != first2 && middle2 != last2) {
 2558         int first1 = first2;
 2559         int last1 = middle2;
 2560         while (first1 < --last1) {
 2561           swapper.swap(first1++, last1);
 2562         }
 2563         first1 = middle2;
 2564         last1 = last2;
 2565         while (first1 < --last1) {
 2566           swapper.swap(first1++, last1);
 2567         }
 2568         first1 = first2;
 2569         last1 = last2;
 2570         while (first1 < --last1) {
 2571           swapper.swap(first1++, last1);
 2572         }
 2573       }
 2574       // end inline
 2575     
 2576       middle = firstCut + (secondCut - middle);
 2577       inplace_merge(first, firstCut, middle, comp, swapper);
 2578       inplace_merge(middle, secondCut, last, comp, swapper);
 2579     }
 2580   
 2581     /**
 2582      * Performs a binary search on an already-sorted range: finds the first position where an element can be inserted
 2583      * without violating the ordering. Sorting is by a user-supplied comparison function.
 2584      *
 2585      * @param first Beginning of the range.
 2586      * @param last  One past the end of the range.
 2587      * @param x     Element to be searched for.
 2588      * @param comp  Comparison function.
 2589      * @return The largest index i such that, for every j in the range <code>[first, i)</code>, <code>comp.apply(array[j],
 2590      *         x)</code> is <code>true</code>.
 2591      * @see Sorting#upper_bound
 2592      */
 2593     static int lower_bound(int first, int last, int x, IntComparator comp) {
 2594       //if (comp==null) throw new NullPointerException();
 2595       int len = last - first;
 2596       while (len > 0) {
 2597         int half = len / 2;
 2598         int middle = first + half;
 2599         if (comp.compare(middle, x) < 0) {
 2600           first = middle + 1;
 2601           len -= half + 1;
 2602         } else {
 2603           len = half;
 2604         }
 2605       }
 2606       return first;
 2607     }
 2608   
 2609     /**
 2610      * Sorts the specified range of elements according to the order induced by the specified comparator.  All elements in
 2611      * the range must be <i>mutually comparable</i> by the specified comparator (that is, <tt>c.compare(a, b)</tt> must
 2612      * not throw an exception for any indexes <tt>a</tt> and <tt>b</tt> in the range).<p>
 2613      *
 2614      * This sort is guaranteed to be <i>stable</i>:  equal elements will not be reordered as a result of the sort.<p>
 2615      *
 2616      * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low
 2617      * sublist is less than the lowest element in the high sublist).  This algorithm offers guaranteed n*log(n)
 2618      * performance, and can approach linear performance on nearly sorted lists.
 2619      *
 2620      * @param fromIndex the index of the first element (inclusive) to be sorted.
 2621      * @param toIndex   the index of the last element (exclusive) to be sorted.
 2622      * @param c         the comparator to determine the order of the generic data.
 2623      * @param swapper   an object that knows how to swap the elements at any two indexes (a,b).
 2624      * @see IntComparator
 2625      * @see Swapper
 2626      */
 2627     public static void mergeSort(int fromIndex, int toIndex, IntComparator c, Swapper swapper) {
 2628       /*
 2629         We retain the same method signature as quickSort.
 2630         Given only a comparator and swapper we do not know how to copy and move elements from/to temporary arrays.
 2631         Hence, in contrast to the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary arrays.
 2632         A non-inplace mergesort would perhaps be faster in most cases, but would require non-intuitive delegate objects...
 2633       */
 2634       int length = toIndex - fromIndex;
 2635     
 2636       // Insertion sort on smallest arrays
 2637       if (length < SMALL) {
 2638         for (int i = fromIndex; i < toIndex; i++) {
 2639           for (int j = i; j > fromIndex && (c.compare(j - 1, j) > 0); j--) {
 2640             swapper.swap(j, j - 1);
 2641           }
 2642         }
 2643         return;
 2644       }
 2645     
 2646       // Recursively sort halves
 2647       int mid = (fromIndex + toIndex) / 2;
 2648       mergeSort(fromIndex, mid, c, swapper);
 2649       mergeSort(mid, toIndex, c, swapper);
 2650     
 2651       // If list is already sorted, nothing left to do.  This is an
 2652       // optimization that results in faster sorts for nearly ordered lists.
 2653       if (c.compare(mid - 1, mid) <= 0) {
 2654         return;
 2655       }
 2656     
 2657       // Merge sorted halves
 2658       inplace_merge(fromIndex, mid, toIndex, c, swapper);
 2659     }
 2660   
 2661     /**
 2662      * Performs a binary search on an already-sorted range: finds the last position where an element can be inserted
 2663      * without violating the ordering. Sorting is by a user-supplied comparison function.
 2664      *
 2665      * @param first Beginning of the range.
 2666      * @param last  One past the end of the range.
 2667      * @param x     Element to be searched for.
 2668      * @param comp  Comparison function.
 2669      * @return The largest index i such that, for every j in the range <code>[first, i)</code>, <code>comp.apply(x,
 2670      *         array[j])</code> is <code>false</code>.
 2671      * @see Sorting#lower_bound
 2672      */
 2673     static int upper_bound(int first, int last, int x, IntComparator comp) {
 2674       //if (comp==null) throw new NullPointerException();
 2675       int len = last - first;
 2676       while (len > 0) {
 2677         int half = len / 2;
 2678         int middle = first + half;
 2679         if (comp.compare(x, middle) < 0) {
 2680           len = half;
 2681         } else {
 2682           first = middle + 1;
 2683           len -= half + 1;
 2684         }
 2685       }
 2686       return first;
 2687     }
 2688   
 2689   }

Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math » [javadoc | source]