クイックソートの実装にMergesortよりも時間がかかるようです

Question

私はクイックソートの実装を行いたいと思いました（小さな配列に対しては3つの分割要素と挿入ソートのメジアンを使用します）、それをMergeSortの実装と比較しますクイックソートの平均時間は、MergeSortのそれよりも良いはずです。実行するたびに、配列をソートするのに（ランダムな順序でも）時間がかかるようです。なぜこれが起こっているのだろうか？

クイックソート：

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); 
    } 
} 

マージ：私は長さ10^8の10個のランダムなアレイは、このアルゴリズムを実行したとき、例えば、マージソートを実行する13385.8ミリ秒の平均を取った

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++]; 
     } 
    } 
} 

、クイックソートは平均14096.7ミリ秒でした。明確にするために

が、これは私は問題があった場所を見つけるために多くのものを試した後、実行時間に

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

を測定する方法で、私は、ランダムな配列を作成した関数を変更し、それが判明します実際にはQuickSortが早く動作します。理由は分かりませんが、アレイを作成した方法がQuickSortのパフォーマンスに悪影響を与えているようです。

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; 
}