Mergesort An Array of Strings in C

Question

I'm trying to implement a merge sort for an array of strings entered from standard input, and am at a loss at what is wrong. Right now I'm facing a segmentation fault. How should I modify my code?

main() {
    char temp;
    int i = 0;
    char Strings[NUM][LEN];

    printf("Please enter %d strings, one per line:\n", NUM);
    for (i; i < 25; i++) {
        fgets(&Strings[i][0], LEN, stdin);
    }

    i = 0;
    puts("\nHere are the strings in the order you entered:");
    for (i; i < 25; i++) {
        printf("%s\n", Strings[i]);
    }

    mergesort(Strings, NUM);

    i = 0;
    puts("\nHere are the strings in alphabetical order");
    for (i; i < 25; i++) {
        printf("%s\n", Strings[i]);
    }
}

int mergesort(char list[NUM][LEN], int length) { // First part
    mergesort_r(0, length, list);
    return 0;
}

int mergesort_r(int left, int right, char list[NUM][LEN]) { // Overloaded portion
    if (right - left <= 1) {
        return 0;
    }

    int left_start  = left;
    int left_end    = (left + right) / 2;
    int right_start = left_end;
    int right_end   = right;

    mergesort_r( left_start, left_end, list);
    mergesort_r( right_start, right_end, list);

    merge(list, left_start, left_end, right_start, right_end);
}

int merge(char list[NUM][LEN], int left_start, int left_end, int right_start, int right_end) {

    int left_length = left_end - left_start;
    int right_length = right_end - right_start;

    char *left_half[left_length];
    char *right_half[right_length];

    int r = 0;
    int l = 0;
    int i = 0;

    for (i = left_start; i < left_end; i++, l++) {
        strcpy(left_half[l], list[i]);
    }

    for (i = right_start; i < right_end; i++, r++) {
        strcpy(right_half[r], list[i]);
    }

    for (i = left_start, r = 0, l = 0; l < left_length && r < right_length; i++) {
        if (strcmp(left_half[l], right_half[r]) < 0) {
            strcpy(list[i], left_half[l++]);
        } else {
            strcpy(list[i], right_half[r++]);
        }
    }

    for ( ; l < left_length; i++, l++) {
        strcpy(list[i], left_half[l]);
    }
    for ( ; r < right_length; i++, r++) {
        strcpy(list[i], right_half[r]);
    }
    return 0;
}

I'm not sure if it's that I'm passing in my array incorrectly, or maybe it's that I am not even executing swaps properly. I'm at my wits end with this and could use some advice.

Solution 1

should be

char left_half[left_length][LEN];
char right_half[right_length][LEN];

Solution 2

#include<stdio.h>
#include<stdlib.h>
#include<string.h> //To use the string functions like strcmp and strcpy

#define MAX 10  // This is the default size of every string 

void Merge(char* arr[],int low,int mid,int high) //Merging the Array Function
{
    int nL= mid-low+1;
    int nR= high-mid;

    char** L=malloc(sizeof(char *)*nL);
    char** R=malloc(sizeof(char *)*nR);
    int i;
    for(i=0;i<nL;i++)
    {
        L[i]=malloc(sizeof(arr[low+i]));
        strcpy(L[i],arr[low+i]);
    }
    for(i=0;i<nR;i++)
    {
        R[i]=malloc(sizeof(arr[mid+i+1]));
        strcpy(R[i],arr[mid+i+1]);
    }
    int j=0,k;
    i=0;
    k=low;
    while(i<nL&&j<nR)
    {
        if(strcmp(L[i],R[j])<0)strcpy(arr[k++],L[i++]);
        else strcpy(arr[k++],R[j++]);
    }
    while(i<nL)strcpy(arr[k++],L[i++]);
    while(j<nR)strcpy(arr[k++],R[j++]);

}


void MergeSort(char* arr[],int low,int high) //Main MergeSort function
{
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(arr,low,mid,high);
    }
}


int main()
{
    printf("\nEnter the size of the array desired: ");
    int size;  //This is the String array size
    scanf("%d",&size);

    char** arr= malloc(sizeof(char *)* size); //Creating required string array
    printf("\nEnter the strings of the array: ");

    int i;
    for(i=0;i<size;i++)
    {
        arr[i]=malloc(sizeof(char)*MAX);
        printf("\nEnter String: ");
        scanf("%s",arr[i]);
    }
    MergeSort(arr,0,size-1);
    printf("\nThe Sorted Array is: ");
    for(i=0;i<size;i++)printf("%s ->",arr[i]);
    return 0;

}

This is a Working solution to the same problem. Hope it Helps! Cheers! :)

Comments

[mah]

Perhaps you should include the output of what you are seeing -- particularly if you run under a debugger so you can get more detailed information about the segfault. That seems nicer than asking people to read your (relatively small, but still) haystack of code looking for a needle of crash.

[Fiddling Bits]

What is NUM #defined to?

[BLUEPIXY]

strcpy(left_half[l] Memory destination indicated by the pointer is not ensured

[user3014886]

That did it! Thanks a lot for the help.