In merge sort algorithm, will freeing the left and right sub arrays after the arrays have been merged make any difference in the space complexity?

Question

In one of the tutorial videos for merge sort, it was mentioned that once the right and left sub arrays have to merged to the parent array, in order to reduce the space complexity we need to free the memory allocated for the left and right sub arrays. But whenever we come out of the function call, the local variable will be destroyed. Do correct me if I am wrong. So will the action of freeing the memory make any difference?

Here is the code that I wrote:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void mergeArr(int *rarr, int *larr, int *arr, int rsize, int lsize) {
    int i = 0, r = 0, l = 0;

    while (r < rsize && l < lsize) {
        if (rarr[r] < larr[l]) {
            arr[i++] = rarr[r++];
        } else {
            arr[i++] = larr[l++];
        }
    }
    while (r < rsize) {
        arr[i++] = rarr[r++];
    }
    while (l < lsize) {
        arr[i++] = larr[l++];
    }
}

void mergeSort(int *arr, int length) {
    if (length > 1) {
        int l1 = length / 2;
        int l2 = length - l1;
        int rarr[l1], larr[l2];

        for (int i = 0; i < l1; i++) {
            rarr[i] = arr[i];
        }
        for (int i = l1; i < length; i++) {
            larr[i - l1] = arr[i];
        }

        mergeSort(rarr, l1);
        mergeSort(larr, l2);
        mergeArr(rarr, larr, arr, l1, l2);
        // will free(rarr); free(larr); make any difference in space complexity
    }
}

int main() {
    int arr[5] = { 1, 10, 2, 7, 5 };
    mergeSort(arr, 5);
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";
}

Answer 1

In your implementation, the left and right arrays are defined with automatic storage, so deallocation is automatic when the function returns but it poses 2 problems:

• a sufficiently large array will invoke undefined behavior because allocating too much space with automatic storage will cause a stack overflow.
• variable sized arrays are not standard C++. You are relying on a compiler specific extension.

The maximum stack space used by your function is proportional to N, so the space complexity is O(N) as expected. You could allocate these arrays with new, and of course you would then have to deallocate them with delete otherwise you would have memory leaks and the amount of memory lost would be proportional to N*log2(N).

An alternative approach would use a temporary array, allocated at the initial call and passed to the recursive function.

Note also that the names for the left and right arrays are very confusing. rarr is actually to the left of larr!

Here is a modified version:

#include <iostream>

using namespace std;

void mergeArr(int *larr, int *rarr, int *arr, int lsize, int rsize) {
    int i = 0, r = 0, l = 0;

    while (l < lsize && r < rsize) {
        if (larr[l] <= rarr[r]) {
            arr[i++] = larr[l++];
        } else {
            arr[i++] = rarr[r++];
        }
    }
    while (l < lsize) {
        arr[i++] = larr[l++];
    }
    while (r < rsize) {
        arr[i++] = rarr[r++];
    }
}

void mergeSort(int *arr, int length) {
    if (length > 1) {
        int l1 = length / 2;
        int l2 = length - l1;
        int *larr = new int[l1];
        int *rarr = new int[l2];

        for (int i = 0; i < l1; i++) {
            larr[i] = arr[i];
        }
        for (int i = l1; i < length; i++) {
            rarr[i - l1] = arr[i];
        }

        mergeSort(larr, l1);
        mergeSort(rarr, l2);
        mergeArr(larr, rarr, arr, l1, l2);
        delete[] larr;
        delete[] rarr;
    }
}

int main() {
    int arr[] = { 1, 10, 2, 7, 5 };
    int length = sizeof arr / sizeof *arr;
    mergeSort(arr, length);
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}