Быстрый поиск медленнее, чем у Mergesort?

Вчера я работал над реализацией быстрой сортировки, а затем запускал ее, ожидая более быстрой работы, чем Mergesort (который я также реализовал). Я запустил два, и, хотя быстродействующая сортировка была быстрее для небольших наборов данных, 44 элемента (и я сделал, убедитесь, что он работает), mergesort стал более быстрым алгоритмом довольно быстро. Меня научили, что quicksort почти всегда «быстрее», чем слияние, и я понимаю, что есть некоторые дебаты по этой теме, но я, по крайней мере, ожидал, что это будет ближе, чем это. Для наборов данных> 10000 элементов слияние было более чем в 4 раза быстрее. Ожидается ли это, или есть ошибка в моем коде quicksort?Быстрый поиск медленнее, чем у Mergesort?

слияние:

public static void mergeSort(int[ ] e) 
{ 
    if (e.length <= 1) return; 
    int[] first = new int[e.length/2]; 
    int[] second = new int[e.length - first.length]; 
    System.arraycopy(e, 0, first, 0, first.length); 
    System.arraycopy(e, first.length, second, 0, second.length); 
    mergeSort(first); 
    mergeSort(second); 
    System.arraycopy(merge(first, second), 0, e, 0, e.length); 
} 

private static int[] merge(int[] first, int[] second) { 
    int iFirst = 0; 
    int iSecond = 0; 
    int iCombined = 0; 

    int[] combined = new int[first.length + second.length]; 
    while(iFirst < first.length && iSecond < second.length) { 
     if (first[iFirst] > second[iSecond]) { 
      combined[iCombined++] = second[iSecond++]; 
     } 
     else combined[iCombined++] = first[iFirst++]; 
    } 
    for(; iFirst < first.length; iFirst++) { 
     combined[iCombined++] = first[iFirst]; 
    } 
    for(; iSecond < second.length; iSecond++) { 
     combined[iCombined++] = second[iSecond]; 
    } 
    return combined; 
}

быстрая сортировка:

public static void quicksort(int[] a, int first, int last) { 
    if (first >= last) return; 

    int partitionIndex = partition(a, first, last); 
    quicksort(a, first, partitionIndex - 1); 
    quicksort(a, partitionIndex + 1, last); 
} 

public static int partition(int[] x, int first, int last) { 
    int left = first; 
    int right = last; 
    int pivot = x[first]; 
    int pivotIdx = first; 

    while(left <= right) { 
     while(left < x.length && x[left] <= pivot) left++; 
     while(right >= 0 && x[right] > pivot) right--; 
     if (left <= right) { 
      int temp = x[left]; 
      x[left] = x[right]; 
      x[right] = temp; 
     } 
    } 
    pivotIdx = right; 
    x[first] = x[right]; 
    x[pivotIdx] = pivot; 
    return pivotIdx; 
}

Быстрый поиск медленнее, чем у Mergesort?

ответ

Смежные вопросы