Java generic 3-median quicksort

Question

My generic 3 median quicksort:

public class Util {
 final static int CUTOFF = 27;
 public static <T extends Comparable<? super T>> void quicksort(T[] a) {
 quicksort(a, 0, a.length - 1);
 }
 private static <T extends Comparable<? super T>> void quicksort(T[] a, int low, int high) {
 if (low + CUTOFF > high) {
 insertionSort(a);
 } else {
 int middle = (low + high) / 2;
 if (a[middle].compareTo(a[low]) < 0) {
 swapReferences(a, low, middle);
 }
 if (a[high].compareTo(a[low]) < 0) {
 swapReferences(a, low, high);
 }
 if (a[high].compareTo(a[middle]) < 0) {
 swapReferences(a, middle, high);
 }
 swapReferences(a, middle, high - 1);
 T pivote = a[high - 1];
 int i, j;
 for (i = low, j = high - 1;;) {
 while (a[++i].compareTo(pivote) < 0);
 while (pivote.compareTo(a[--j]) < 0);
 if (i >= j) {
 break;
 }
 swapReferences(a, i, j);
 }
 swapReferences(a, i, high - 1);
 quicksort(a, low, i - 1);
 quicksort(a, i + 1, high);
 }
 }
 private static <T extends Comparable<? super T>> void swapReferences(T a[], int x, int y) {
 T temp = a[x];
 a[x] = a[y];
 a[y] = temp;
 }
 private static <T extends Comparable<? super T>> void insertionSort(T a[]) {
 for (int p = 1; p < a.length; p++) {
 T tmp = a[p];
 int j = p;
 for (; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
 a[j] = a[j - 1];
 }
 a[j] = tmp;
 }
 }
}

My testing code

import java.util.Random;
import java.util.Arrays;
public class PruebaTiempo {
 private static <T extends Comparable<? super T>> int binarySearch(T a[], T x) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
 mid = (low + high) / 2;
 int cmp = a[mid].compareTo(x);
 if (cmp < 0) {
 low = mid + 1;
 } else if (cmp > 0) {
 high = mid - 1;
 } else {
 return mid;
 }
 }
 return -1;
 }
 private static <T extends Comparable<? super T>> int linearSearch(T a[], T x) {
 for (int i = 0; i < a.length; i++) {
 if (a[i].compareTo(x) == 0) {
 return i;
 }
 }
 return -1;
 }
 public static void main(String[] args) {
 Random rd = new Random();
 long t1, t2;
 for (int k = 50000; k <= 1000000; k += 50000) {
 int arr[] = rd.ints(k, 10000, 1000000).toArray();
 Integer array[] = Arrays.stream(arr).boxed().toArray(Integer[]::new);
 Integer array2[]=Arrays.copyOf(array, array.length);
 t1 = System.currentTimeMillis();
 Util.quicksort(array);
 t2 = System.currentTimeMillis();
 System.out.println("Tiempo quicksort: " + (t2 - t1) + "ms");
 t1 = System.currentTimeMillis();
 Arrays.sort(array2);
 t2 = System.currentTimeMillis();
 System.out.println("Tiempo sort: " + (t2 - t1) + "ms");
 }
 }
}

I know they are different sorts, but they should have similar running times. In my PC the results are:

Tiempo quicksort: 1663ms
Tiempo sort: 21ms
Tiempo quicksort: 14986ms
Tiempo sort: 71ms
Tiempo quicksort: 27422ms
Tiempo sort: 186ms

Answer 1

The error was in this line:

 if (low + CUTOFF > high) {
 insertionSort(a);

It should had been

if (low + CUTOFF > high) {
 insertionSort(a,low,high);

And the corresponding change to insertionSort