Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
   /*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package org.apache.mahout.math;
  
  
  
  public final class Sorting {
    
    /* Specifies when to switch to insertion sort */
    private static final int SIMPLE_LENGTH = 7;
    static final int SMALL = 7;
    
    private Sorting() {}
    
    private static <T> int med3(T[] arrayint aint bint cComparator<T> comp) {
      T x = array[a];
      T y = array[b];
      T z = array[c];
      int comparisonxy = comp.compare(xy);
      int comparisonxz = comp.compare(xz);
      int comparisonyz = comp.compare(yz);
      return comparisonxy < 0 ? (comparisonyz < 0 ? b
          : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
          : (comparisonxz > 0 ? c : a));
    }
    
    private static int med3(byte[] arrayint aint bint cByteComparator comp) {
      byte x = array[a];
      byte y = array[b];
      byte z = array[c];
      int comparisonxy = comp.compare(xy);
      int comparisonxz = comp.compare(xz);
      int comparisonyz = comp.compare(yz);
      return comparisonxy < 0 ? (comparisonyz < 0 ? b
          : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
          : (comparisonxz > 0 ? c : a));
    }
    
    private static int med3(char[] arrayint aint bint cCharComparator comp) {
      char x = array[a];
      char y = array[b];
      char z = array[c];
      int comparisonxy = comp.compare(xy);
      int comparisonxz = comp.compare(xz);
      int comparisonyz = comp.compare(yz);
      return comparisonxy < 0 ? (comparisonyz < 0 ? b
          : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
          : (comparisonxz > 0 ? c : a));
    }
    
    private static int med3(double[] arrayint aint bint c,
        DoubleComparator comp) {
      double x = array[a];
      double y = array[b];
      double z = array[c];
      int comparisonxy = comp.compare(xy);
      int comparisonxz = comp.compare(xz);
      int comparisonyz = comp.compare(yz);
      return comparisonxy < 0 ? (comparisonyz < 0 ? b
          : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
          : (comparisonxz > 0 ? c : a));
    }
    
    private static int med3(float[] arrayint aint bint c,
        FloatComparator comp) {
      float x = array[a];
      float y = array[b];
      float z = array[c];
      int comparisonxy = comp.compare(xy);
      int comparisonxz = comp.compare(xz);
      int comparisonyz = comp.compare(yz);
      return comparisonxy < 0 ? (comparisonyz < 0 ? b
          : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
          : (comparisonxz > 0 ? c : a));
   }
   
   private static int med3(int[] arrayint aint bint cIntComparator comp) {
     int x = array[a];
     int y = array[b];
     int z = array[c];
     int comparisonxy = comp.compare(xy);
     int comparisonxz = comp.compare(xz);
     int comparisonyz = comp.compare(yz);
     return comparisonxy < 0 ? (comparisonyz < 0 ? b
         : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
         : (comparisonxz > 0 ? c : a));
   }
  
  
This is used for 'external' sorting. The comparator takes indices, not values, and compares the external values found at those indices.

Parameters:
a
b
c
comp
Returns:
 
   private static int med3(int aint bint cIntComparator comp) {
     int comparisonab = comp.compare(ab);
     int comparisonac = comp.compare(ac);
     int comparisonbc = comp.compare(bc);
     return comparisonab < 0
         ? (comparisonbc < 0 ? b : (comparisonac < 0 ? c : a))
         : (comparisonbc > 0 ? b : (comparisonac > 0 ? c : a));
   }
   
   private static int med3(long[] arrayint aint bint cLongComparator comp) {
     long x = array[a];
     long y = array[b];
     long z = array[c];
     int comparisonxy = comp.compare(xy);
     int comparisonxz = comp.compare(xz);
     int comparisonyz = comp.compare(yz);
     return comparisonxy < 0 ? (comparisonyz < 0 ? b
         : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
         : (comparisonxz > 0 ? c : a));
   }
   
   private static int med3(short[] arrayint aint bint c,
       ShortComparator comp) {
     short x = array[a];
     short y = array[b];
     short z = array[c];
     int comparisonxy = comp.compare(xy);
     int comparisonxz = comp.compare(xz);
     int comparisonyz = comp.compare(yz);
     return comparisonxy < 0 ? (comparisonyz < 0 ? b
         : (comparisonxz < 0 ? c : a)) : (comparisonyz > 0 ? b
         : (comparisonxz > 0 ? c : a));
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the byte array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparison that determines the sort.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(byte[] arrayint startint end,
       ByteComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void checkBounds(int arrLengthint startint end) {
     if (start > end) {
       // K0033=Start index ({0}) is greater than end index ({1})
       throw new IllegalArgumentException("Start index " + start
           + " is greater than end index " + end);
     }
     if (start < 0) {
       throw new ArrayIndexOutOfBoundsException("Array index out of range "
           + start);
     }
     if (end > arrLength) {
       throw new ArrayIndexOutOfBoundsException("Array index out of range "
           + end);
     }
   }
   
   private static void quickSort0(int startint endbyte[] arrayByteComparator comp) {
     byte temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     byte partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }

  
  
Sorts some external data with QuickSort.

Parameters:
start the start index to sort.
end the last + 1 index to sort.
comp the comparator.
swap an object that can exchange the positions of two items.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(int startint endIntComparator compSwapper swap) {
     checkBounds(end + 1, startend);
     quickSort0(startendcompswap);
   }
   
   private static void quickSort0(int startint endIntComparator compSwapper swap) {
     int length = end - start;
     if (length < 7) {
       insertionSort(startendcompswap);
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         // for lots of data, bottom, middle and top are medians near the beginning, middle or end of the data
         int skosh = length / 8;
         bottom = med3(bottombottom + skoshbottom + (2 * skosh), comp);
         middle = med3(middle - skoshmiddlemiddle + skoshcomp);
         top = med3(top - (2 * skosh), top - skoshtopcomp);
       }
       middle = med3(bottommiddletopcomp);
     }
 
     int partitionIndex = middle// an index, not a value.
     
     // regions from a to b and from c to d are what we will recursively sort
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (b <= c) {
       // copy all values equal to the partition value to before a..b.  In the process, advance b
       // as long as values less than the partition or equal are found, also stop when a..b collides with c..d
       int comparison;
       while (b <= c && (comparison = comp.compare(bpartitionIndex)) <= 0) {
         if (comparison == 0) {
           if (a == partitionIndex) {
             partitionIndex = b;
           } else if (b == partitionIndex) {
             partitionIndex = a;
           }
           swap.swap(ab);
           a++;
         }
         b++;
       }
       // at this point [start..a) has partition values, [a..b) has values < partition
       // also, either b>c or v[b] > partition value
 
       while (c >= b && (comparison = comp.compare(cpartitionIndex)) >= 0) {
         if (comparison == 0) {
           if (c == partitionIndex) {
             partitionIndex = d;
           } else if (d == partitionIndex) {
             partitionIndex = c;
           }
           swap.swap(cd);
 
           d--;
         }
         c--;
       }
       // now we also know that [d..end] contains partition values,
       // [c..d) contains values > partition value
       // also, either b>c or (v[b] > partition OR v[c] < partition)
 
       if (b <= c) {
         // v[b] > partition OR v[c] < partition
         // swapping will let us continue to grow the two regions
         if (c == partitionIndex) {
           partitionIndex = b;
         } else if (b == partitionIndex) {
           partitionIndex = d;
         }
         swap.swap(bc);
         b++;
         c--;
       }
     }
     // now we know
     // b = c+1
     // [start..a) and [d..end) contain partition value
     // all of [a..b) are less than partition
     // all of [c..d) are greater than partition
 
     // shift [a..b) to beginning
     length = Math.min(a - startb - a);
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       swap.swap(lh);
       l++;
       h++;
     }
 
     // shift [c..d) to end
     length = Math.min(d - cend - 1 - d);
     l = b;
     h = end - length;
     while (length-- > 0) {
       swap.swap(lh);
       l++;
       h++;
     }
 
     // recurse left and right
     length = b - a;
     if (length > 0) {
       quickSort0(startstart + lengthcompswap);
     }
 
     length = d - c;
     if (length > 0) {
       quickSort0(end - lengthendcompswap);
     }
   }

  
In-place insertion sort that is fast for pre-sorted data.

Parameters:
start Where to start sorting (inclusive)
end Where to stop (exclusive)
comp Sort order.
swap How to swap items.
 
   private static void insertionSort(int startint endIntComparator compSwapper swap) {
     for (int i = start + 1; i < endi++) {
       for (int j = ij > start && comp.compare(j - 1, j) > 0; j--) {
         swap.swap(j - 1, j);
       }
     }
   }
  
Sorts the specified range in the array in a specified order.

Parameters:
array the char array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(char[] arrayint startint endCharComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void quickSort0(int startint endchar[] arrayCharComparator comp) {
     char temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     char partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the double array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparison.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
See also:
java.lang.Double.compareTo(java.lang.Double)
 
   public static void quickSort(double[] arrayint startint endDoubleComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void quickSort0(int startint enddouble[] arrayDoubleComparator comp) {
     double temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     double partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(partionValuearray[b])) >= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the float array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparator.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(float[] arrayint startint endFloatComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void quickSort0(int startint endfloat[] arrayFloatComparator comp) {
     float temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j], array[j - 1]) < 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     float partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(partionValuearray[b])) >= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the int array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparator.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(int[] arrayint startint endIntComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void quickSort0(int startint endint[] arrayIntComparator comp) {
     int temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     int partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the long array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparator.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static void quickSort(long[] arrayint startint endLongComparator comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static void quickSort0(int startint endlong[] arrayLongComparator comp) {
     long temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
         middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
         top = med3(arraytop - (2 * length), top - lengthtopcomp);
       }
       middle = med3(arraybottommiddletopcomp);
     }
     long partionValue = array[middle];
     int a = start;
     int b = a;
     int c = end - 1;
     int d = c;
     while (true) {
       int comparison;
       while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
         if (comparison == 0) {
           temp = array[a];
           array[a++] = array[b];
           array[b] = temp;
         }
         b++;
       }
       while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
         if (comparison == 0) {
           temp = array[c];
           array[c] = array[d];
           array[d--] = temp;
         }
         c--;
       }
       if (b > c) {
         break;
       }
       temp = array[b];
       array[b++] = array[c];
       array[c--] = temp;
     }
     length = a - start < b - a ? a - start : b - a;
     int l = start;
     int h = b - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     length = d - c < end - 1 - d ? d - c : end - 1 - d;
     l = b;
     h = end - length;
     while (length-- > 0) {
       temp = array[l];
       array[l++] = array[h];
       array[h++] = temp;
     }
     if ((length = b - a) > 0) {
       quickSort0(startstart + lengtharraycomp);
     }
     if ((length = d - c) > 0) {
       quickSort0(end - lengthendarraycomp);
     }
   }
  
  
Sorts the specified range in the array in a specified order.

Parameters:
array the array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
comp the comparator.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
 
   public static <T> void quickSort(T[] arrayint startint endComparator<T> comp) {
     Preconditions.checkNotNull(array);
     checkBounds(array.lengthstartend);
     quickSort0(startendarraycomp);
   }
   
   private static final class ComparableAdaptor<T extends Comparable<? super T>>
       implements Comparator<T>, Serializable {
     
     @Override
     public int compare(T o1, T o2) {
       return o1.compareTo(o2);
     }
     
   }
  
  
Sort the specified range of an array of object that implement the Comparable interface.

Parameters:
<T> The type of object.
array the array.
start the first index.
end the last index (exclusive).
 
   public static <T extends Comparable<? super T>> void quickSort(T[] arrayint startint end) {
     quickSort(arraystartendnew ComparableAdaptor<T>());
   }
   
   private static <T> void quickSort0(int startint end, T[] arrayComparator<T> comp) {
     T temp;
     int length = end - start;
     if (length < 7) {
       for (int i = start + 1; i < endi++) {
         for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
           temp = array[j];
           array[j] = array[j - 1];
           array[j - 1] = temp;
         }
       }
       return;
     }
     int middle = (start + end) / 2;
     if (length > 7) {
       int bottom = start;
       int top = end - 1;
       if (length > 40) {
         length /= 8;
         bottom = med3(arraybottombottom + lengthbottom + (2 * length),
             comp);
        middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
        top = med3(arraytop - (2 * length), top - lengthtopcomp);
      }
      middle = med3(arraybottommiddletopcomp);
    }
    T partionValue = array[middle];
    int a = start;
    int b = a;
    int c = end - 1;
    int d = c;
    while (true) {
      int comparison;
      while (b <= c && (comparison = comp.compare(array[b], partionValue)) <= 0) {
        if (comparison == 0) {
          temp = array[a];
          array[a++] = array[b];
          array[b] = temp;
        }
        b++;
      }
      while (c >= b && (comparison = comp.compare(array[c], partionValue)) >= 0) {
        if (comparison == 0) {
          temp = array[c];
          array[c] = array[d];
          array[d--] = temp;
        }
        c--;
      }
      if (b > c) {
        break;
      }
      temp = array[b];
      array[b++] = array[c];
      array[c--] = temp;
    }
    length = a - start < b - a ? a - start : b - a;
    int l = start;
    int h = b - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    length = d - c < end - 1 - d ? d - c : end - 1 - d;
    l = b;
    h = end - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    if ((length = b - a) > 0) {
      quickSort0(startstart + lengtharraycomp);
    }
    if ((length = d - c) > 0) {
      quickSort0(end - lengthendarraycomp);
    }
  }
  
  
Sorts the specified range in the array in ascending numerical order.

Parameters:
array the short array to be sorted.
start the start index to sort.
end the last + 1 index to sort.
Throws:
java.lang.IllegalArgumentException if start > end.
java.lang.ArrayIndexOutOfBoundsException if start < 0 or end > array.length.
  public static void quickSort(short[] arrayint startint endShortComparator comp) {
    Preconditions.checkNotNull(array);
    checkBounds(array.lengthstartend);
    quickSort0(startendarraycomp);
  }
  
  private static void quickSort0(int startint endshort[] arrayShortComparator comp) {
    short temp;
    int length = end - start;
    if (length < 7) {
      for (int i = start + 1; i < endi++) {
        for (int j = ij > start && comp.compare(array[j - 1], array[j]) > 0; j--) {
          temp = array[j];
          array[j] = array[j - 1];
          array[j - 1] = temp;
        }
      }
      return;
    }
    int middle = (start + end) / 2;
    if (length > 7) {
      int bottom = start;
      int top = end - 1;
      if (length > 40) {
        length /= 8;
        bottom = med3(arraybottombottom + lengthbottom + (2 * length),
            comp);
        middle = med3(arraymiddle - lengthmiddlemiddle + lengthcomp);
        top = med3(arraytop - (2 * length), top - lengthtopcomp);
      }
      middle = med3(arraybottommiddletopcomp);
    }
    short partionValue = array[middle];
    int a = start;
    int b = a;
    int c = end - 1;
    int d = c;
    while (true) {
      int comparison;
      while (b <= c && (comparison = comp.compare(array[b], partionValue)) < 0) {
        if (comparison == 0) {
          temp = array[a];
          array[a++] = array[b];
          array[b] = temp;
        }
        b++;
      }
      while (c >= b && (comparison = comp.compare(array[c], partionValue)) > 0) {
        if (comparison == 0) {
          temp = array[c];
          array[c] = array[d];
          array[d--] = temp;
        }
        c--;
      }
      if (b > c) {
        break;
      }
      temp = array[b];
      array[b++] = array[c];
      array[c--] = temp;
    }
    length = a - start < b - a ? a - start : b - a;
    int l = start;
    int h = b - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    length = d - c < end - 1 - d ? d - c : end - 1 - d;
    l = b;
    h = end - length;
    while (length-- > 0) {
      temp = array[l];
      array[l++] = array[h];
      array[h++] = temp;
    }
    if ((length = b - a) > 0) {
      quickSort0(startstart + lengtharraycomp);
    }
    if ((length = d - c) > 0) {
      quickSort0(end - lengthendarraycomp);
    }
  }

  
Perform a merge sort on the specified range of an array.

Parameters:
<T> the type of object in the array.
array the array.
start first index.
end last index (exclusive).
comp comparator object.
  @SuppressWarnings("unchecked"// required to make the temp array work, afaict.
  public static <T> void mergeSort(T[] arrayint startint endComparator<T> comp) {
    checkBounds(array.lengthstartend);
    int length = end - start;
    if (length <= 0) {
      return;
    }
    
    T[] out = (T[]) new Object[array.length];
    System.arraycopy(arraystartoutstartlength);