Implementation of quicksort seems to be taking more time than Mergesort

Question

I was trying to do an implementation of QuickSort (with median of 3 partitioning-element and insertion sort for small arrays) and compare it to an implementation of MergeSort, but even when QuickSort average time should be better than that of MergeSort, every time I execute it, it seems to be taking more time to sort an array (even one in random order). Any idea why can this be happening?

QuickSort:

public class Quick {

    private static final int M = 10;
    private static Random random = new Random();

    public void sort(int[] a) {
        sort(a, 0, a.length - 1);
        insertionSort(a, 0, a.length - 1);
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi - lo <= 10) return;
        swap(a, lo, pivot(a, lo, hi));
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo;
        while (i <= gt) {
            if      (a[i] < v) swap(a, lt++, i++);
            else if (a[i] > v) swap(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }

    private int pivot(int[] a, int lo, int hi) {
        int     r1 = random.nextInt(hi - lo) + lo,
                r2 = random.nextInt(hi - lo) + lo,
                r3 = random.nextInt(hi - lo) + lo;
        return median3(a, r1, r2, r3);
    }

    private void swap(int[] a, int i, int j) {
        if (i == j) return;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static int median3(int[] a, int i, int j, int k) {
        return (a[i] < a[j] ?
                (a[j] < a[k] ? j : a[i] < a[k] ? k : i) :
                (a[k] < a[j] ? j : a[k] < a[i] ? k : i));
    }

    private void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && a[j] < a[j-1]; j--)
                swap(a, j, j-1);
    }
}

MergeSort:

public class Merge {

    public void sort(int[] a) {
        int[] aux = new int[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        // Merge
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)           a[k] = aux[j++];
            else if (j > hi)            a[k] = aux[i++];
            else if (aux[j] < aux[i])   a[k] = aux[j++];
            else                        a[k] = aux[i++];
        }
    }
}

For example, when I ran this algorithms for 10 random arrays of length 10^8, MergeSort took an average of 13385.8 ms to execute, while QuickSort took an average of 14096.7 ms.

To clarify, this is how I measured execution times

public static void main(String[] args) {
    int pow = (int) Math.pow(10, 8);
    int[] a, b;
    double[]    m1 = new double[10],
                m2 = m1.clone(),
    double st, et;
    Merge merge = new Merge();
    Quick quick = new Quick();
    for (int i = 0; i < 10; i++) {
        a = randomArray(pow);
        b = a.clone();
        st = currentTimeMillis();
        merge.sort(a);
        et = currentTimeMillis();
        m1[i] = et - st;
        st = currentTimeMillis();
        quick.sort(b);
        et = currentTimeMillis();
        m2[i] = et - st;
    }
    out.println("MergeSort: " + mean(m1));
    out.println("QuickSort: " + mean(m2));
}
private static int[] randomArray(int n) {
    r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < a.length; i++) a[i] = r.nextInt();
    return a;
}

Answer 1

After trying lots of things to find out where the issue was, I changed the function that created the random array, and it turns out QuickSort actually works faster now. I don't really know why, but it seems that the way I created the array adversely affected the performance of QuickSort. Now, what I did was that instead of generating an array of random integers, I generated an array form 1 to n and then shuffled it, as follows:

public static int[] permutation(int n) {
    int[] a = new int[n];

    for (int i = 0; i < n; ++i)  a[i] = i + 1;

    for (int i = 0; i < n; i++) {
        int r = i + rnd.nextInt(n - i),
            tmp = a[i];

        a[i] = a[r];
        a[r] = tmp;
    }

    return a;
}