c - 我不明白这一步，特别是在合并排序中

Question

这个问题已经有答案了:

How does the Pseudocode for merge sort work? (2 个回答)

已关闭 6 年前。

在上面的代码中我不明白这一点。它再次调用归并排序，但是当函数重复调用归并排序时，合并何时发挥作用 但是什么时候合并发生我无法理解的代码是递归代码，在分成两半并重复调用合并排序并破坏 inrtoa 单个元素合并后如何发挥作用。真正的问题是真实如何发挥作用

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

#define MAX_SIZE 50000

void merge (int arr[], int start, int mid, int end){
    /* two sorted arrays arr[start ... mid]
       and arr[mid+1 ... end] merge them */
    int tempvals[MAX_SIZE];
    int ptr1, ptr2, ptrnew=0, idx;

    ptr1 = start;
    ptr2 = mid+1;

    /* compare both the sorted arrays element by element
       move the element that is smaller to the new aray */
    while ( (ptr1 <= mid) && (ptr2 <= end)){
        /* compare elements at ptr1 and ptr2 */
        if (arr[ptr1] < arr[ptr2]){
            tempvals[ptrnew] = arr[ptr1];
            ptr1 ++; ptrnew++;
        } else {
            tempvals[ptrnew] = arr[ptr2];
            ptr2 ++; ptrnew++;
        }
    }
    /* at this point --> one of the pointers has reached the end */
    while (ptr1 <= mid){
        tempvals[ptrnew] = arr[ptr1];
        ptr1 ++; ptrnew++;
    } 
    while (ptr2 <= end){
        tempvals[ptrnew] = arr[ptr2];
        ptr2 ++; ptrnew++;
    }

    /* transfer back to arr */
    for (idx = start, ptrnew = 0; idx <= end; idx++, ptrnew++)
        arr[idx] = tempvals[ptrnew];
}

void merge_sort (int arr[], int start, int end){
    int mid = (start + end)/2;
    /* termination condition */
    if( start >= end) return;

    /* recurse */
    merge_sort(arr,start, mid); /* first half */
    merge_sort (arr, mid+1, end); /* second half */
    merge (arr, start, mid, end); /* do the merging */
}
void print_array (int arr[], int size){
    int i;
    for (i=0; i < size; i++)
        printf ("%d ",arr[i]);
    printf ("\n");
}
int main(){
    int arr[MAX_SIZE]; 
    int i;
    /* initialize */
    for (i=0; i < MAX_SIZE; i++)
        arr[i] = rand(); 

    /* sort and print */
    merge_sort (arr,0, MAX_SIZE - 1);
}

Blockquote

在上面的代码中我不明白这一点 它再次调用归并排序，但是当函数重复调用归并排序时，合并何时发挥作用

/* recurse */
    merge_sort(arr,start, mid); /* first half */
    merge_sort (arr, mid+1, end); /* second half */
    merge (arr, start, mid, end); /* do the merging */

Answer 1

它在注释recurse下，并在逐行注释中调用。您重复使用 merge_sort 对数组的左侧部分和右侧部分进行排序。然后你调用合并来重新组合它们，现在按顺序排列。

您不会永远调用merge_sort:注意merge_sort顶部的基本情况(也称为终止条件):

if( start >= end) return;

当你到达一个不超过一个元素的列表时，你只需返回——它已经是有序的了。然后你爬回那个大的调用链，合并单个元素，然后合并更大的列表，......直到完成。