cpp - Implement a merge sort function without using void return type (recursively)

Question

I intend to create a recursive merge sort function that returns a pointer to the sorted array. Below is my implementation of the program.

The output produced by the code mostly consists of garbage memory locations. Since it is a recursive function, I'm having trouble debugging it. What scares me is whether I have understood pointers, arrays and their interconversion incorrectly. It would be really helpful if someone could take a look at the code and tell me my mistake.

Function that prints an array given a pointer to its first element

void printArr(int *arr, int n){
    int *ptr = arr;
    for(int i = 0; i < n; i++){
        cout << *ptr << " ";
        ptr++;
    }
    cout << endl;
}

Merge Sort function

Here p is the pointer to the given array, n is the length of the array. l and r are the indices of the first and last element of the array respectively.

// returns pointer to the sorted array
int* mergeSort(int *p, int n, int l, int r){
    if(l >= r){
        return &p[l];
    }
    int mid = l + (r-l)/2;
    int *leftArray = mergeSort(p, n, l, mid);
    int *rightArray = mergeSort(p, n, mid+1, r);
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int sortedArray[n1+n2];
    int *ptr = sortedArray; // pointer to the sorted array

    int p1 = 0; // left array index pointer
    int p2 = 0; // right array index pointer
    int idx = 0; // sorted array index pointer
    int flag = 0; /* flag = 1 => all elements of left array have been placed into the sorted array ; flag = 2 => all elements of right array have been placed into the sorted array */

    // putting elements into the sorted array
    for(int i = 0; i < n1+n2; i++){

        if(p1 == n1){
            flag = 1;
            break;
        }
        if(p2 == n2){
            flag = 2;
            break;
        }

        if(*(leftArray+i) > *(rightArray+i)){
            sortedArray[i] = *(leftArray+p1);
            p1++;
            idx++;
        }
        else{
            sortedArray[i] = *(rightArray+p2);
            p2++;
            idx++;
        }
    }

    if(flag == 1){
        // put remaining elements of right array into the sorted array
        for(int i = idx; i < n1+n2; i++){
            sortedArray[i] = *(rightArray+p2);
            p2++;
        }
    }
    if(flag == 2){
        // put remaining elements of left array into the sorted array
        for(int i = idx; i < n1+n2; i++){
            sortedArray[i] = *(leftArray+p1);
            p1++;
        }
    }
    // return the sorted array
    return ptr;
}

Main function

    int main(){
        int arr[] = {7,2,1,5};
        int n = sizeof(arr)/sizeof(int);
        int *p = arr;
        cout << "Original array: ";
        printArr(arr, n);
        int *f = mergeSort(arr, n, 0, 3);
        cout << "New array: ";
        printArr(f, n);
    }

Answer 1

Your code have returned the local array's address, which is invalidated after function returned. Then gabarage data is printed:

    int sortedArray[n1+n2];
    int *ptr = sortedArray; // pointer to the sorted array

Change into

int *ptr = new int[n1 + n2];
auto sortedArray = ptr;

Then we get a non-garbage value, but we hit memory leak and it's hard to deal with memory deallocation since the retuned pointer may point to the array p under certain boundary conditions.

So return pointer is not a good design, and it just wastes the API call to allocate memory and deallocate memory. It's better to split the function into two: the first one allocates a temporary buffer, and the second one handles sorting with the buffer as a parameter and calls itself with a recursive. Or just sort in place, totally avoid the temporary buffer.