为什么随着输入规模的增长，mergesort 比 quicksort 表现更好？

Question

我正在用 C 编写一些数据结构，我想我会比较 mergesort 与 quicksort。在这里，“向量”是以下结构：

typedef struct vector {
    int* vec;
    int len;
    int cap;
} Vector;

int* vec

最初被分配

1024 * sizeof(int)

，当它达到容量时，它将内存重新分配到一个可以容纳两倍数量的整数的空间。

static void double_vec_cap(Vector* vec) {
    int* new_ptr = realloc(vec->vec, (sizeof(int) * (u_int64_t) vec->cap * 2));
    if (new_ptr == NULL) {
        printf("Error: realloc failed in vector_double_vec_cap\n");
    }
    else {
        vec->vec = new_ptr;
        vec->cap *= 2;
    }
    return;
}

以下是快排算法：

static void quicksort(int arr[], int left, int right) {
    if (right < left) return;
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
    i++;
    int temp = arr[i];
    arr[i] = arr[right];
    arr[right] = temp;
    quicksort(arr, left, i - 1);
    quicksort(arr, i + 1, right);
}

void sort_vector_quicksort(Vector* vec) {
    quicksort(vec->vec, 0, vec->len - 1);
    return;
}

下面是mergesort算法：

static int* merge(int* left_arr, int left_arr_len, int* right_arr, int right_arr_len) {
    int* result = malloc(sizeof(int) * (u_int64_t) (left_arr_len + right_arr_len));
    int i = 0; int l = 0; int r = 0;

    while (l < left_arr_len && r < right_arr_len) {
        if (left_arr[l] <= right_arr[r]) {
            result[i] = left_arr[l];
            i++; l++;
        } else {
            result[i] = right_arr[r];
            i++; r++;
        }
    }
    while (l < left_arr_len) {
        result[i] = left_arr[l];
        i++; l++;
    }
    while (r < right_arr_len) {
        result[i] = right_arr[r];
        i++; r++;
    }  

    free(left_arr);
    left_arr = NULL;
    free(right_arr);
    right_arr = NULL;
    return result; 
}

static int* ds_mergesort(int* arr, int length) {
    if (length <= 1) return arr;
    int mid = length / 2;
    
    int* left_arr = malloc(sizeof(int) * (u_int64_t) mid);
    int* right_arr = malloc(sizeof(int) * (u_int64_t) (length - mid));
    int j = 0;
    for (int i = 0; i < length; i++) {
        if (i < mid) {
            left_arr[i] = arr[i];
        } else {
            right_arr[j] = arr[i];
            j++;
        }
    }
    free(arr);
    arr = NULL;
    left_arr = ds_mergesort(left_arr, mid);
    right_arr = ds_mergesort(right_arr, length - mid);
    
    return merge(left_arr, mid, right_arr, (length - mid));
}

void sort_vector_mergesort(Vector* vec) {
    vec->vec = ds_mergesort(vec->vec, vec->len);
    return;
}

我认为，因为快速排序就地进行排序，所以它总是比合并排序执行得更快，因为后者除了排序之外还必须处理内存分配，直到“向量”大小达到大约500,000。 这是我得到的结果。

Sorting Exponetially larger vectors

Vector size: 1024
Mergesort Time: 0.000318s  Quicksort Time: 0.000062s
Quicksort was faster than Mergesort by: 0.000256s
----------------------------------------------------

Vector size: 2048
Mergesort Time: 0.000638s  Quicksort Time: 0.000127s
Quicksort was faster than Mergesort by: 0.000511s
----------------------------------------------------

Vector size: 4096
Mergesort Time: 0.001377s  Quicksort Time: 0.000265s
Quicksort was faster than Mergesort by: 0.001112s
----------------------------------------------------

Vector size: 8192
Mergesort Time: 0.003064s  Quicksort Time: 0.000539s
Quicksort was faster than Mergesort by: 0.002525s
----------------------------------------------------

Vector size: 16384
Mergesort Time: 0.005424s  Quicksort Time: 0.001347s
Quicksort was faster than Mergesort by: 0.004077s
----------------------------------------------------

Vector size: 32768
Mergesort Time: 0.010996s  Quicksort Time: 0.002865s
Quicksort was faster than Mergesort by: 0.008131s
----------------------------------------------------

Vector size: 65536
Mergesort Time: 0.022966s  Quicksort Time: 0.007522s
Quicksort was faster than Mergesort by: 0.015444s
----------------------------------------------------

Vector size: 131072
Mergesort Time: 0.045921s  Quicksort Time: 0.021228s
Quicksort was faster than Mergesort by: 0.024693s
----------------------------------------------------

Vector size: 262144
Mergesort Time: 0.098435s  Quicksort Time: 0.067185s
Quicksort was faster than Mergesort by: 0.031250s
----------------------------------------------------

Vector size: 524288
Mergesort Time: 0.186068s  Quicksort Time: 0.230357s
Mergesort was faster than Quicksort by: 0.044289s
----------------------------------------------------

Vector size: 1048576
Mergesort Time: 0.377109s  Quicksort Time: 0.853521s
Mergesort was faster than Quicksort by: 0.476412s
----------------------------------------------------

Vector size: 2097152
Mergesort Time: 0.765805s  Quicksort Time: 3.259530s
Mergesort was faster than Quicksort by: 2.493725s
----------------------------------------------------

Vector size: 4194304
Mergesort Time: 1.534298s  Quicksort Time: 12.558161s
Mergesort was faster than Quicksort by: 11.023863s
----------------------------------------------------

Vector size: 8388608
Mergesort Time: 3.118347s  Quicksort Time: 48.325201s
Mergesort was faster than Quicksort by: 45.206854s
----------------------------------------------------

与归并排序相比，快速排序最终需要更长的时间来对大小为 8,388,608 的数组进行排序。我不知道与内存缓存有关吗？对此或我如何实现这些功能的任何想法将不胜感激。我确实尝试过使用不同的枢轴进行快速排序，随机选择一个索引，三个中等，然后只选择最后一个索引。选择最后一个索引似乎是最有效的，大概是因为数组中的数字都是随机的。