相同的 MergeSort 实现在 C 中运行良好，但在 Java 中花费大量时间

Question

我一直在学习算法和数据结构课程，我决定在 C 和 Java 中实现 MergeSort 以实践我所学的知识。这个想法是构建一个包含随机整数的指定大小的向量，然后使用算法对其进行排序。

我遇到的问题是，对于大小为 100 或更大的数组，MergeSort 需要巨大的时间才能在 Java 中结束，而在 C 中立即结束。对于“大量”时间，我的意思是我只能等待大小低于 40 的输入，否则我不得不终止该过程，因为几分钟后它还没有完成。不过，我使用的实现是相同的，它是我们在课程中教过的实现，它采用 Θ(nlogn) 而不是就地。

我担心 Java 中的幕后发生了一些事情，因为每次调用 Merge 过程时我都会分配一个新数组，但我无法解释为什么 C 中也没有发生这种情况.

这是 Java 代码：

public class MergeSort {

    public static void main(String[] args) {
        System.out.println("Building array...");
        int v[] = randomArray(200);
        System.out.println("Sorting...");
        mergeSort(v, 0, v.length-1);
        System.out.println("Array sorted!");
        System.out.println(Arrays.toString(v));
    }

    public static void mergeSort(int[] A, int p, int q){
        if(p < q){
            int r = (p+q)/2;
            mergeSort(A, 0, r);
            mergeSort(A, r+1, q);
            merge(A, p, r, q);
        }
    }

    public static void merge(int[] A, int p, int r, int q){
        int[] B = new int[q-p+1];
        int k = 0;
        int i = p;
        int j = r+1;

        while(i <= r && j <= q){
            if(A[i] < A[j]){
                B[k] = A[i];
                i++;
            }else{
                B[k] = A[j];
                j++;
            }
            k++;
        }

        while(i <= r){
            B[k] = A[i];
            i++;
            k++;
        }

        while(j <= q){
            B[k] = A[j];
            j++;
            k++;
        }
        
        // Copies the merged array back to A
        for(int a=p; a<=q; a++){
            A[a] = B[a-p];
        }
    }

    public static int[] randomArray(int size){
        Random rand = new Random();
        int v[] = new int[size];
        for(int i=0; i<size; i++){
            v[i] = Math.abs(rand.nextInt());
        }
        return v;
    }
}

这是 C 的：

void printvector(int *a, int l){
    printf("[ ");
    for(int i=0; i<l; i++){
        printf("%d ", *(a+i));
    }
    printf(" ]\n");
}

void Merge(int *A, int p, int r, int q){
    int B[q-p+1];
    int k = 0;
    int i = p;
    int j = r+1;
    
    while(i <= r && j <= q) {
        if(A[i] < A[j]){
            B[k] = A[i];
            i++;
        }else{
            B[k] = A[j];
            j++;
        }
        k++;
    }

    while(i <= r){
        B[k] = A[i];
        i++;
        k++;
    }

    while(j <= q){
        B[k] = A[j];
        j++;
        k++;
    }

    // Copies the merged array back to A
    for(int a=p; a<=q; a++){
        A[a] = B[a-p];
    }
}

void MergeSort(int *A, int p, int q){
    if (p < q) {
        int r = (p+q)/2;
        MergeSort(A, p, r);
        MergeSort(A, r+1, q);   
        Merge(A, p, r, q);
    }
}


int main(){
    int size = 200;
    int array[size];

    // Building random vector
    srand(time(NULL));
    for(int i=0; i<size; i++){
        array[i] = abs(rand());
    }

    MergeSort(array,0, size-1); 

    printf("Sorted vector: ");
    printvector(array, size);
    return 0;
}

Answer 1

    public static void mergeSort(int[] A, int p, int q){
        if(p < q){
            int r = (p+q)/2;
            mergeSort(A, 0, r);
            mergeSort(A, r+1, q);
            merge(A, p, r, q);
        }
    }

在java版本中，mergeSort(A, 0, r);应该是mergeSort(A, p, r);

相同的 MergeSort 实现在 C 中运行良好，但在 Java 中花费大量时间

Same MergeSort implementation works fine in C but takes a lot of time in Java

c

java

sorting

algorithm

mergesort