Why is there segmentation fault in this merge sort?

Question

I compiled this code on different compilers, but all of them gave runtime error. Can someone tell me what's wrong with this code?

void merge(int *str, int beg, int mid, int end) {
 int *arr = new int[end - beg + 1];
 int k = 0;
 int i = beg;
 int j = mid + 1;
 while (i <= mid && j <= end) {
 if (str[i] < str[j]) {
 arr[k] = str[i];
 i++;
 k++;
 } else {
 arr[k] = str[j];
 j++;
 k++;
 }
 }
 while (i <= mid) {
 arr[k] = str[i];
 i++;
 k++;
 }
 while (j <= end) {
 arr[k] = str[j];
 //here i got buffer overrun while writing to arr
 j++;
 k++;
 }
 for (i = beg; i <= end; i++) {
 str[i] = arr[i - beg];
 }
 delete[] arr;
}
void merge_sort(int *str, int beg, int end) {
 
 if (beg >= end)
 return;
 int mid = (end - beg) / 2;
 merge_sort(str, beg, mid);
 merge_sort(str, mid + 1, end);
 merge(str, beg, mid, end);
}

This code is almost same as I found on Sanfoundry, but that one is working but mine got some errors.

• Dai: Protip: Instead of this int* arr = new int[end - beg + 1]; use std::vector instead.
• Dai: I assume you're implementing merge-sort as a learning exercise (which is fine, otherwise I'd be telling you to use <algorithm>'s std::merge premade implementation) - is that the case? Anyway, you should be using size_t instead of int to represent offsets and indexes - not least because it helps prevent confusing int data values with their incomparable offset values.
• n. m. could be an AI: int mid = (end - beg) / 2; is wrong.

Answer 1

Your computation of the mid point in merge_sort is incorrect: instead of int mid = (end - beg) / 2; you should write:

 int mid = beg + (end - beg) / 2;

Note also that your API is confusing as mid seems to be the end of the index of the last element of the left half and end the index of the last element of the right slice. It is much simpler and less error prone to specify mid as the index of the first element of the right half and end the index of the first element after the right slice. With this convention, the initial call is:

 merge_sort(array, 0, array_length);

Here is a modified version using type size_t for index and length variables:

void merge(int *str, size_t beg, size_t mid, size_t end) {
 int *arr = new int[end - beg];
 size_t i = beg;
 size_t j = mid;
 size_t k = 0;
 while (i < mid && j < end) {
 if (str[i] <= str[j]) {
 arr[k++] = str[i++];
 } else {
 arr[k++] = str[j++];
 }
 }
 while (i < mid) {
 arr[k++] = str[i++];
 }
 while (j < end) {
 arr[k++] = str[j++];
 }
 for (i = beg; i < end; i++) {
 str[i] = arr[i - beg];
 }
 delete[] arr;
}
void merge_sort(int *str, size_t beg, size_t end) {
 if (end - beg >= 2) {
 size_t mid = beg + (end - beg) / 2;
 merge_sort(str, beg, mid);
 merge_sort(str, mid, end);
 merge(str, beg, mid, end);
 }
}