#include <stdio.h>

void msort(int *a, int n);
void msort_recursion(
    int a[], int left,
    int right); 
void merge_arrays(int a[], int left, int middle,
                  int right); // merges the sorted portions of the array

int main() {

  int a[] = {5, 2, 4, 1, 3};
  int n = 5;

  msort(a, n);

 
  printf("[");
  for (int i = 0; i < n; i  )

    if (i == n - 1) {
      printf("%d", a[i]);
    } else {
      printf("%d, ", a[i]);
    }
  printf("]\n");

  return 0;
}

void msort(int *a, int n) { msort_recursion(a, 0, n - 1); }

void msort_recursion(int a[], int left, int right) {


  if (left < right) {

    int middle = left   (right - 1) / 2;
    msort_recursion(a, left, middle); 
    msort_recursion(a, middle   1,
                    right); 

    merge_arrays(a, left, middle,
                 right); 
  }
}

void merge_arrays(
    int a[], int left, int middle,
    int right) { 

  int left_size = middle - left   1; 
  int right_size = right - middle;   

  int templ[left_size];
  int tempr[right_size];

  int i, j, k; 

  for (int i = 0; i < left_size; i  )
  
    templ[i] = a[left   i];

  for (int i = 0; i < right_size; i  )
 
    tempr[i] = a[middle   1   i];


  for (i = 0, j = 0, k = left; k <= right; k  ) {

    if ((i < left_size) && (j >= right_size || templ[i] <= tempr[j])) {

      a[k] = templ[i];
      i  ;

    } else {
      a[k] = tempr[j];
      j  ;
    }
  }
}

Merge sort is implemented in Code, but when run, I receive the error code "signal: segmentation fault (core dumped)" which to my understanding, means that it has reached past the end of an array but I do not understand how this is... Merge sort is implemented in Code, but when run, I receive the error code "signal: segmentation fault (core dumped)" which to my understanding, means that it has reached past the end of an array but I do not understand how this is...

CodePudding user response：

for msort_recursion, I was doing int middle = left (right - 1) / 2 instead of int middle = left (right - left) / 2

#include <stdio.h>

void msort(int *a, int n); // merge sort array a with n elements in place in C
void msort_recursion(int a[], int left, int right); // recursion where the array is continuously divided in half
                // until there is only one element left
void merge_arrays(int a[], int left, int middle, int right); // merges the sorted portions of the array

int main() {

  int a[] = {5, 2, 4, 1, 3};
  int n = 5;

  msort(a, n);

  // print sorted array
 for (int i = 0; i < n; i  )
    printf("%d ", a[i]);
  printf("\n");

  return 0;
}

void msort(int *a, int n) { 
 
  msort_recursion(a, 0, n - 1); 
  
}

void msort_recursion(int a[], int left, int right) {

  // as long as the left is less than the right, we will continuously divide the
  // array
  if (left < right) {

    int middle = left   (right - left) / 2; // find the middle of the array
    msort_recursion(a, left, middle); // recursion on the left side of the array
    msort_recursion(a, middle   1, right); // recursion on the right side of the array

    merge_arrays(a, left, middle, right); // merge the sorted sections of the array
  }
}

void merge_arrays(int a[], int left, int middle, int right) { // left is the index for the start of the array, middle is the
                 // middle index, right is the index of the last element in the
                 // right section of the array

  int left_size = middle - left   1; // size of left side of array
  int right_size = right - middle;   // size of right side of the array

  // create 2 tepm sub arrarys and copy the portions into the sub arrays
  int templ[left_size];
  int tempr[right_size];

  int i, j, k; // i is keeping track of left array, j is keeping track of right
               // array, k is keeping track of original array a

  for (int i = 0; i < left_size; i  )
    // copy left side into left temp array
    templ[i] = a[left   i];

  for (int i = 0; i < right_size; i  )
    // copy right side into right temp array
    tempr[i] = a[middle   1   i];

  // pick from the sorted left and right arrays to replace into the original
  // array

  for (i = 0, j = 0, k = left; k <= right; k  ) {

    if ((i < left_size) && (j >= right_size || templ[i] <= tempr[j])) {
      // if the element in the left array is smaller than the element in the
      // right array then replace it in array a as long as we don't reach the end
      // of either the left or right arrays
      a[k] = templ[i];
      i  ;
      // otherwise, put the right element into the array a
    } else {
      a[k] = tempr[j];
      j  ;
    }
  }
}

CodePudding user response：

The reason is you called msort_recursion recursively to many times this happened because the middle is computed wrong and should be int middle = left (right - left) / 2; notice it's the difference in position split in half. make sure to read geeksforgeeks.org/merge-sort more carefully next time

void msort_recursion(int a[], int left, int right) {
    if (left < right) {
        int middle = left   (right - 1) / 2;
        /* Here should be    ^^^^^^^^^ right - left */
        msort_recursion(a, left, middle); 
        msort_recursion(a, middle   1,right); 
        merge_arrays(a, left, middle,right); 
    }
}