合并排序 - 得到不正确的结果和损坏的数据（复制元素）

Question

我尝试实现基本的合并排序，但是出了点问题，它错误地复制了我的输入数组中的一些元素，甚至更改了一些元素，因此输出数组被破坏了。我使用 tmp[] 作为全局声明的数组指针（long *tmp; -> 在全局声明中）我遗漏了什么或做错了什么？

另外，如何提高这个算法的时间复杂度？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void merge(long *arr, int l, int m, int r);
void mergeSort(long *arr, int l, int r);

//Global Declarations
long *tmp;

//Merge Sort
void Merge_Sort(long *Array, int Size) {
    tmp = malloc(sizeof(long) * Size);
    mergeSort(Array, 0, Size - 1);
}

//Merge Sort helper function
void mergeSort(long *arr, int l, int r) {
    if (l >= r)
        return;
    // divide the array into two arrays
    // call mergeSort with each array
    // merge the two arrays into one

    int m = l + ((r - l) / 2; //integer overflow

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
} 

//merge function
static void merge(long *arr, int l, int m, int r) {   
    //tmp[] is a global array with the same size as arr[]
    memcpy(&tmp[l], &arr[l], m - l + 1); //copy left subarray to tmp
    memcpy(&tmp[m + 1], &arr[m + 1], r - m); //copy right subarray to tmp

    int i = l;
    int j = m + 1;
    for (int k = l; k <= r; k++) {
        if (i > m)
            arr[k] = tmp[j++]; //if the left sub-array is exhausted
        else
        if (j > r)
            arr[k] = tmp[i++]; //if the right sub-array is exhausted
        else
        if (tmp[j] < tmp[i])
            arr[k] = tmp[j++]; //compare the current values
        else
            arr[k] = tmp[i++];
    }
}

int main() {
    long array[10] = {
        -3153274050600690459,
        6569843820458972605,
        -6837880721686463424,
        1876340121514080353,
        -1767506107468465601,
        -1913444019437311076,
        -426543213433372251,
        6724963487502039099,
        -1272217999899710623,
        3399373277871640777,
    };
    Merge_Sort(array, 10);
    for (int i = 0; i < 10; i++) {
         printf("%ld\n". array[i]);
    }
    return 0;
}

输出（不正确）：

-1913444019437311076
-426543213433372251
140464981228095
140388532523709
94285492859968
94285492861503
-1767506107468465601
6724963487502039099
-1272217999899710623
3399373277871640777

预期输出：

-6837880721686463424
-3153274050600690459
-1913444019437311076
-1767506107468465601
-1272217999899710623
-426543213433372251
1876340121514080353
3399373277871640777
6569843820458972605
6724963487502039099

Answer 1

merge 函数没有复制正确的字节数：

memcpy(&tmp[l], &arr[l], m - l + 1); //copy left subarray to tmp
memcpy(&tmp[m + 1], &arr[m + 1], r - m); //copy right subarray to tmp

您必须通过将元素数乘以元素大小来计算正确的字节数。另请注意，左右子数组是连续的，因此编写就足够了：

memcpy(&tmp[l], &arr[l], sizeof(*tmp) * (r - l + 1));

还有其他问题：

避免使用全局变量 tmp，只需将其作为额外参数传递给 mergeSort
您必须在 mergeSort() 完成后释放临时数组。

这是修改后的版本：

#include <stdlib.h>
#include <string.h>

//merge function
static void merge(long *arr, int l, int m, int r, long *tmp) {   
    //tmp[] is a global array with the same size as arr[]
    memcpy(&tmp[l], &arr[l], sizeof(*tmp) * (r - l + 1));

    for (int k = l, i = l, j = m + 1; k <= r; k++) {
        if (i <= m && (j > r || tmp[i] <= tmp[j]))
            arr[k] = tmp[i++];
        else
            arr[k] = tmp[j++];
    }
}

//Merge Sort helper function
static void mergeSort(long *arr, int l, int r, long *tmp) {
    if (l < r) {
        // divide the array into two arrays
        // call mergeSort with each array
        // merge the two arrays into one
        int m = l + (r - l) / 2; //avoid integer overflow

        mergeSort(arr, l, m, tmp);
        mergeSort(arr, m + 1, r, tmp);
        merge(arr, l, m, r);
    }
} 

//Merge Sort
void Merge_Sort(long *array, int size) {
    long *tmp = malloc(sizeof(*tmp) * size);
    mergeSort(array, 0, Size - 1, tmp);
    free(tmp);
}

关于你的另一个问题：如何提高这个算法的时间复杂度？

合并排序算法的时间复杂度为 O(N * log(N))，与集合分布无关。这被认为是通用数据的最佳选择。如果您的数据恰好具有已知的特定特征，则其他算法的复杂度可能较低。

如果所有值都在一个小范围内，counting sort 是一个不错的选择
如果有很多重复项和少量K个不同的唯一值，复杂度可以降低到O(N + K.log(K))。
整数值可以用 radix sort 排序，这对于大型数组更有效。
如果数组几乎已排序，insertion sort 或修改后的合并排序（通过一次初始测试测试左右子数组是否已经有序）也可以更快。
使用 Timsort 可以加快许多非随机分布的执行速度。

这里是 radix_sort() 对 long 数组的实现：

#include <stdlib.h>
#include <string.h>

void radix_sort(long *a, size_t size) {
    size_t counts[sizeof(*a)][256] = {{ 0 }}, *cp;
    size_t i, sum;
    unsigned int n;
    unsigned long *tmp, *src, *dst, *aa;

    dst = tmp = malloc(size * sizeof(*a));
    src = (unsigned long *)a;
    for (i = 0; i < size; i++) {
        unsigned long v = src[i] + (unsigned long)VAL_MIN;
        for (n = 0; n < sizeof(*a) * 8; n += 8)
            counts[n >> 3][(v >> n) & 255]++;
    }
    for (n = 0; n < sizeof(*a) * 8; n += 8) {
        cp = &counts[n >> 3][0];
        for (i = 0, sum = 0; i < 256; i++)
            cp[i] = (sum += cp[i]) - cp[i];
        for (i = 0; i < size; i++)
            dst[cp[((src[i] + (unsigned long)VAL_MIN) >> n) & 255]++] = src[i];
        aa = src;
        src = dst;
        dst = aa;
    }
    if (src == tmp)
        memcpy(a, src, size * sizeof(*a));
    free(tmp);
}

合并排序 - 得到不正确的结果和损坏的数据（复制元素）

Merge Sort - getting incorrect results and corrupted data (duplicating the elements)

c

algorithm

mergesort

data-structures