Merge Sort is Susceptible to Stack Overflow

Merge sort is an easy-to-implement stable sorting algorithm which is particularly useful in competitive programming when you want to count reverse pairs. Proficient programmer can coding and debugging it within even 5 minutes. The following is a typical implementation of merge sort in C.

#include <stdlib.h>
#include <time.h>

void merge_sort(int *arr, int low, int high) {
    // base case
    if (high <= low) {
        return;
    }

    // recursive case
    int mid = (low + high) / 2;
    merge_sort(arr, low, mid);
    merge_sort(arr, mid + 1, high);

    // -- merge
    int buffer[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            buffer[k++] = arr[i++];
        } else {
            buffer[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        buffer[k++] = arr[i++];
    } 
    while (j <= high) {
        buffer[k++] = arr[j++];
    }

    // -- copy back
    for (k = 0; k < high - low + 1; k++) {
        arr[low + k] = buffer[k];
    }

    return;
}

int main() {
    int len = 4000000;
    int *arr = malloc(len * sizeof(int));
    
    srand((unsigned int) time(NULL));
    for (int i = 0; i < len; i++) {
        arr[i] = rand();
    }

    merge_sort(arr, 0, len - 1);

    return 0;
}

Looks good... right? If you directly compile and run this code, you will end up with segmentation fault.

$ gcc -Wall -Wextra -Wpedantic -Werror -std=gnu17 -O2 main.c -o main
$ ./main
Segmentation fault (core dumped)

But why? Notice that len in main() is a pretty large number, and the space complexity of out implementation is O(len) due to the stack allocated array buffer in merge_sort(). The default stack capacity in many systems is 8MiB. We can verify this by ourselves.

$ ulimit -s
8192

ulimit is a Bash built-in command. With -s option, it will tell us the stack capacity for a process forked from shell in KiB. We type in ./main in the shell and hit Enter. The shell calls fork() first to copy itself to spawn a child process, and then child process calls execv() to replace the program with ./main. So, the default stack capacity for ./main is also 8MiB.

However, int buffer[4000000] is about 15MiB, which exceeds the 8MiB limit. The most portable fix of this issue it to allocate the buffer on the heap instead of stack.

#include <stdlib.h>
...
void merge_sort(int *arr, int low, int high) {
    ...
    int *buffer = malloc((high - low + 1) * sizeof(int));
    ...
    free(buffer); // DO NOT forget this!
    return;
}
...

Compile and run the code again, we won't have any issues.

$ gcc -Wall -Wextra -Wpedantic -Werror -std=gnu17 -O2 main.c -o main
$ ./main
$ echo $?
0