C ++ - Почему функция слияния обращает массив после его рекурсивного вызова?

Question

У меня есть следующие функции, которые реализуют сортировку слиянием:

Первая функция - это функция слияния, а вторая - функция слияния.

Как показанона выходе, когда массив [-3,8] попадает внутрь функции слияния, он, кажется, обращается к [8, -3], что делает сортировку невозможной.

• входной массивis int array [5] = {37, 45, 29, 8, -3};

• Ожидаемый результат будет: Sorted Array:-3 8 29 27 45

...

Слияние: ... || arr1: 8 ||arr2: -3 -------- NEW: -------- -3 8

Слияние: ... || arr1: 29 || arr2: 8 -3 -------- NEW: -------- 8 -3 29

Слияние: ... || arr1: 37 45||arr2: 29 8 -3 -------- NEW: -------- 29 8 -3 37 45

Sorted Array: 29 8 -3 37 45

объединить:

int * ArraySort::merge(int arr1[], int arr1_size, int arr2[], int arr2_size){

    std::cout<<"\nMerging: ... ";
    int * new_array = new int [arr1_size+arr2_size];
    int i = 0, j = 0, k = 0;

    std::cout<<"||arr1: ";
    for(int i=0;i<arr1_size;i++)
        std::cout<<arr1[i]<<" ";

    std::cout<<"|| arr2: ";
    for(int i=0;i<arr2_size;i++)
        std::cout<<arr2[i]<<" ";


    while(i<arr1_size && j<arr2_size){
        if(arr1[i] < arr2[j]){
            new_array[k++] = arr1[i++];
        }
        else{
            new_array[k++] = arr2[j++];
        }
    }

    //    Clean up
    while(i<arr1_size){
        new_array[k++] = arr1[i++];
    }
    while(j<arr2_size){
        new_array[k++] = arr2[j++];
    }

    std::cout<<"\n -------- NEW: -------- ";
    for(int i=0;i<arr1_size+arr2_size;i++)
        std::cout<<new_array[i]<<" ";
    std::cout<<"\n";

    return new_array;
}

объединитьСортировать:

int * ArraySort::mergeSort(int * arr, int size){
    std::cout<<"\n\nMerge Sort...\n";
    std::cout<<"ON: ";
    for(int i=0;i<size;i++){
        std::cout<<arr[i]<<" ";
    }

    if(size == 1)
          return arr;

    int mid = size/2;
    std::cout<<"\nMid:"<<mid;

    int * left = new int[mid];
    int * right = new int [size-mid];

    std::cout<<"\nLEFT: ";
    for(int i=0;i<mid;i++){
        left[i] = arr[i];
        std::cout<<left[i]<<" ";
    }
    std::cout<<"\nRIGHT: ";
    for(int i=mid;i<size;i++){
        right[i-mid] = arr[i];
        std::cout<<right[i-mid]<<" ";
    }
    mergeSort(left, mid);
    mergeSort(right, size-mid);

    return merge(left, mid, right, size-mid);
}

Answer 1

Ваша функция mergeSort возвращает значение int *, которое игнорируется в режиме рекурсии.Когда вы вызываете mergeSort в той же функции, возвращаемые значения теряются, и новые объединенные массивы никогда не будут получены для следующего сравнения.

замените эти строки буксировки, чтобы исправить ошибку в функции mergeSort.

/* the problem is here, when the return values are ignored 
       the arrays are getting sorted but never actually updated */
    left = mergeSort(left, mid);
    right = mergeSort(right, size-mid);

Вся функция

int * ArraySort::mergeSort(int * arr, int size){
    std::cout<<"\n\nMerge Sort...\n";
    std::cout<<"ON: ";
    for(int i=0;i<size;i++){
        std::cout<<arr[i]<<" ";
    }

    if(size == 1)
          return arr;

    int mid = size/2;
    std::cout<<"\nMid:"<<mid;

    int * left = new int[mid];
    int * right = new int [size-mid];

    std::cout<<"\nLEFT: ";
    for(int i=0;i<mid;i++){
        left[i] = arr[i];
        std::cout<<left[i]<<" ";
    }
    std::cout<<"\nRIGHT: ";
    for(int i=mid;i<size;i++){
        right[i-mid] = arr[i];
        std::cout<<right[i-mid]<<" ";
    }
    /* the problem is here, when the return values are ignored 
       the arrays are getting sorted but never actually updated */
    left = mergeSort(left, mid);
    right = mergeSort(right, size-mid);

    return merge(left, mid, right, size-mid);
}

вывод

Слияние Сортировка ... ВКЛ .: -3 Слияние: ... || arr1: 8 ||arr2: -3 -------- NEW: -------- -3 8

Слияние: ... || arr1: 29 ||arr2: -3 8 -------- NEW: -------- -3 8 29

Слияние: ... || arr1: 37 45 ||arr2: -3 8 29 -------- NEW: -------- -3 8 29 37 45