Implementacja quicksorta wydaje się zabierać więcej czasu niż Mergesort

Question

Próbowałem wykonać implementację QuickSort (z medianą 3 elementów partycjonowania i sortowania wstawek dla małych tablic) i porównać ją z implementacją MergeSort, ale nawet wtedy, gdy Średni czas QuickSort powinien być lepszy niż MergeSort, za każdym razem, gdy go wykonuję, wydaje się, że potrzeba więcej czasu, aby posortować tablicę (nawet jedną w przypadkowej kolejności). Każdy pomysł, dlaczego tak się dzieje?

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

Na przykład, gdy uruchomiony ten algorytm dla 10 losowych macierzy o długości 10^8 mergesort trwało średnio 13385.8 ms wykonując natomiast QuickSort trwało średnio 1406,7.7 ms.

celu wyjaśnienia, to w jaki sposób mierzone czasy wykonania

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

Po wypróbowaniu wiele rzeczy, aby dowiedzieć się, gdzie problem był, zmieniłem funkcję, która stworzyła losowych tablicę, a okazuje się, QuickSort obecnie działa teraz szybciej. Naprawdę nie wiem dlaczego, ale wydaje się, że sposób, w jaki utworzyłem macierz, negatywnie wpłynął na wydajność QuickSort. Teraz, co zrobiłem było to, że zamiast generowania liczb losowych tablicę, to wygenerowany formularz tablicy 1 do n, a następnie tasuje je w następujący sposób:

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