Issue

This Content is from Stack Overflow. Question asked by Julia Navarro

#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++;
    }
  }
}

Solution

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++;
    }
  }
}

 This Question was asked in  StackOverflow by  Julia Navarro and Answered by Julia Navarro It is licensed under the terms of 
CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.