c - merge_sort 不起作用，输出只是一堆 1 -1 和 0

Question

所以我得到了以递归方式编写 merge_sort 的任务，它只返回与 0,-1, 1 长度相同的数组原始输入。有什么想法我做错了什么吗？ input_merge_sort.h 和input_merge_sort.c 由任务给出并处理输入和输出，所以我只需要关注算法本身。有关该算法的一些细节，以确保我理解正确:

MergeSort 通过将列表拆分为大小相等的列表来对列表进行排序，拆分它们直到它们成为单个元素，然后将 2 个单个元素列表放在一起，比较它们并将较小的列表放在前面。使用子列表，您通过从 2 个子列表中读取，比较值并将指针 1 元素进一步写入原始列表，然后将其与另一个子列表的旧元素进行比较，该元素比另一个大。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "input_merge_sort.h"
/*
    array:  Pointer at the start of the array
    first:  Index of the first element
    len  :  Index of the last element
*/

void merge(int a[], int i1, int j1, int j2) {
    int temp[j2 - i1];    //array used for merging
    int i, j, k;
    i = i1;    //beginning of the first list
    int i2 = j1 + 1;
    j = i2;    //beginning of the second list
    k = 0;

    while (i <= j1 && j <= j2) {    //while elements in both lists
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= j1)    //copy remaining elements of the first list
        temp[k++] = a[i++];

    while (j <= j2)    //copy remaining elements of the second list
        temp[k++] = a[j++];

    //Transfer elements from temp[] back to a[]
    for (i = i1, j = 0; i <= j2; i++, j++)
        a[i] = temp[j];
}

void merge_sort(int *array, int first, int last) {
    int middle;
    if (first < last) {
        middle = ((first + last) / 2);
        merge_sort(array, first, middle);
        merge_sort(array, middle + 1, last);
        merge(array, first, middle, last);
    }
}

/*
Reads integers from files and outputs them into the stdout after mergesorting them.

How to run: ./introprog_merge_sort_rekursiv <max_amount>  <filepath>
*/
int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("usage: %s <max_amount>  <filepath>\n", argv[0]);
        exit(2);
    }

    char *filename = argv[2];

    // Initialize array
    int *array = (int*)malloc(atoi(argv[1]) * sizeof(int));        //MINE
    int len = read_array_from_file(array, atoi(argv[1]), filename);

    printf("Input:\n");
    print_array(array, len);

    // Call of "merge_sort()"
    merge_sort(array, array[0], array[len - 1]); //MINE

    printf("Sorted:\n");
    print_array(array, len);
    free(array);
    return 0;
}

Answer 1

merge_sort 函数将数组及其第一个和最后一个元素的索引作为参数，但您传递的是元素本身。变化:

merge_sort(array, array[0],array[len-1]);

到:

merge_sort(array, 0, len - 1);

在 merge 中，您在堆栈上创建了一个临时数组，但它只有一个元素。应该是:

int temp[j2 - i1 + 1];

我建议您更改函数，这样它们就不会将最后一个元素作为上限，而是将第一个元素作为上限，这在 C 数组和循环中很常见。在我看来，这使代码更简单。数组的两半是 [low, mid) 和 [mid, high)。整个数组的长度是high - low。