void merge_sort(int* arr, int start, int stop){ // [start; stop]
    int min_array_size = 8;

    std::cout << start << " " << stop << std::endl;

    if ((stop - start   1) > min_array_size){
        merge_sort(arr, start, start   ((stop-start 1) / 2) - 1);
        merge_sort(arr, start   ((stop-start 1) / 2), stop);

        std::cout << "merging: " << start << " " << stop << std::endl;

        int left_index = start;
        int right_index = start   ((stop-start 1) / 2);

        int* new_arr = new int[stop-start   1];

        std::cout << "New_arr created!\n";

        for (int i = start; i <= stop; i  ){
            if (arr[left_index] < arr[right_index]){
                new_arr[i] = arr[left_index];
                left_index  ;
            }
            else {
                new_arr[i] = arr[right_index];
                right_index  ;
            }

            if (left_index == start   ((stop-start 1) / 2)){
                i  ;
                for (int j = i; j <= stop; j  , i  ){
                    new_arr[j] = arr[right_index  ];
                }
            }
            if (right_index > stop){
                i  ;
                for (int j = i; j <= stop; j  , i  ){
                    new_arr[j] = arr[left_index  ];
                }
            }
        }

        for (int i = start; i <= stop; i  ){
            arr[i] = new_arr[i];
            std::cout << "arr[" << i << "] = " << arr[i] << std::endl;
        }

        delete[] new_arr;

        std::cout << "memory cleaned!\n";

    }
    else{
        selection_sort(arr   start, (stop - start   1));
        for (int i = 0; i < (stop - start)   1; i  ){
            std::cout << arr[i   start] << " ";
        }
        std::cout << std::endl;
    }
}

Can someone please tell me why it says the following if I clean memory with delete[] new_arr?

malloc(): corrupted top size

I really can't understand why it is so.

Here is my insertion_sort() code:

void selection_sort(int* arr, size_t size){
    for (int i = 0; i < size - 1; i  ){
        int min_index = i;
        for (int j = i   1; j < size; j  ){
            if (arr[j] < arr[min_index]){
                min_index = j;
            }
        }
        if (min_index != i){
            std::swap(arr[i], arr[min_index]);
        }
    }
}

https://godbolt.org/z/Wj56MM349

CodePudding user response：

You're overflowing your heap allocations, corrupting the heap, and breaking things eventually. The problem is:

1. You allocate an array with stop - start 1 elements (meaning valid indices run from 0 to stop - start.
2. In the subsequent loop (for (int i = start; i <= stop; i ){), you assign to any and all array indices from start to stop (inclusive on both ends).

If start is not 0, then assignment to new_arr[stop] is definitely an out-of-bounds write; the larger start gets, the more invalid indices you'll see.

The problem would rarely occur as a result of a single call (the heap metadata being corrupted would be for a subsequent heap element, not the one containing new_arr), but with the recursive calls you have plenty of opportunities to do terrible things to the heap and break it faster. Even a single such out-of-bounds write puts you in nasal demons territory, so you need to fix your code to avoid doing it even once.