CODEWITHSUNDEEP
calgorithmsortingsegmentation-faultmergesort
Shannon
Shannon

Reputation: 119

I am getting a Segmentation fault (core dumped) error with dynamically allocated arrays for merge sort in C?

I think I have stared at this long enough to make my eyes roll to the back of my head. I am trying to implement an ascending merge sort using dynamically allocated arrays, and although (I believe) my logic behind the algorithm is correct, I am getting the segmentation fault (core dumped) error. I know that it means somewhere I have a pointer pointing somewhere it shouldn't or vice versa, but I cannot seem to figure it out. Suggestions?

Main

int main(int argc, char *argv[])
{
  int my_array[ARRAY_SIZE];
  bool sorted = false;

  if( argc != 2)
    {
      printf("Program usage: %s sortname\n", argv[0]);
      return 1;
    }

  // Fill array with random numbers
  initArray(my_array, ARRAY_SIZE);

  // Sort array by chosen algorithm
  if(strcmp(argv[1], "bubble") == 0)
  {
    bubbleSort(my_array, ARRAY_SIZE);
  }
  else if(strcmp(argv[1], "merge") == 0)
    {  
      mergeSort(my_array, ARRAY_SIZE);
    }
  else
    {
      printf("Invalid sort algorithm. Must specifiy 'bubble' or 'merge'\n");
      return 1;
    }

  // Test if array is sorted correctly
  sorted = verifySort(my_array, ARRAY_SIZE);


  if(sorted)
    printf("Congrats! Array is sorted correctly\n");
  else
    printf("*** Error: Array sort algorithm fails verification test ***\n");

  return 0;
}

Merge Sort

//mergeSort is what I call from main, the array that is passed in is defined as: 
//int my_array[ARRAY_SIZE]; 
//It is filled with random numbers and passed into mergeSort
void mergeSort(int *array_start, int array_size)
{
    printf("Using merge sort algorithm...\n");

    int min = 0;
    int max = array_size-1;

    mergeSortHelper(array_start, min, max);
}

void mergeSortHelper(int *array_start, int min, int max)
{   
    int mid;

    if (min<max)
    {
        mid = (max+min)/2;
        //split into two halves
        mergeSortHelper(array_start, min, mid);     //left half
        mergeSortHelper(array_start, mid+1, max);   //right half
        merge(array_start, min, mid, max);
    }
}

void merge(int *array_start, int min, int mid, int max)
{
    int i, j, k, left, right;

    left = mid - min + 1;
    right = max - mid;

    int *leftArray = calloc(left, sizeof(int));
    int *rightArray = calloc(right, sizeof(int));

    //copy to left temp array
    for(i = 0; i < left; i++)
    {
        leftArray[i] = array_start[min+1];
    }

    //copy to right temp array
    for(j = 0; j < right; j++)
    {
        rightArray[j] = array_start[mid+1+j];
    }

    i = 0;
    j = 0;
    k = min;

    //merge temp arrays 
    while(i < left && j < right)
    {
        if(leftArray[i] <= rightArray[j])
        {
            array_start[k] = leftArray[i];
            i++;
        }
        else
        {
            array_start[k] = rightArray[j];
            j++;
        }
        k++;
    }

    //copy extra elements back to array
    while (i < left)
    {
        array_start[k] = leftArray[j];
        j++;
        k++;
    }

    while (j < right)
    {
        array_start[k] = rightArray[j];
        j++;
        k++;
    }

    free(leftArray);
    free(rightArray);
}

Upvotes: 1

Views: 394

Answers (1)

Joe Farrell
Joe Farrell

Reputation: 3542

while (i < left)
{
    array_start[k] = leftArray[j];
    j++;
    k++;
}

This looks like an infinite loop to me. There's nothing inside of it that changes the value of i or left, so eventually k or j grows large enough to cause the fault.

Upvotes: 3

Related Questions