Try to sort strings with merge sort

Question

How do I sort a 2D-array(strings) using merge sort?

e.g.

arr[0] = "foo";
arr[1] = "bar";

and I hope it to be like

arr[0] = "bar";
arr[1] = "foo";

after being sorted but it doesn't work

Need some help here.

The following is my code for merge sort:

char * tem[10]; // global
void merge(char * arr[], int s1, int e1, int s2, int e2)
{
    int index = s1;
    int k = s1; //record where to start for the for loop int the bottom
    while(s1 <= e1 && s2 <= e2)
    {
        int i = 0, j = 0;
        while(arr[s1][i] != '\0' && arr[s2][j] != '\0')
        { 
            //compare each character in the string

            if(arr[s1][i] < arr[s2][j])
            {
                tem[index] = arr[s1];
                s1++;
                index++;
                break;
            }
            else if(arr[s1][i] > arr[s2][j])
            {
                tem[index] = arr[s2];
                s2++;
                index++;
                break;
            }
            else
            {
                i++;
                j++;
            }
        }

        //if one string contains the other
        if(arr[s1][i] == '\0' && arr[s2][j] != '\0') //if the first string is shorter
        {
            tem[index] = arr[s1];
            s1++;
            index++;
        }
        else if(arr[s1][i] != '\0' && arr[s2][j] == '\0') //if the second one is shorter
        {
            tem[index] = arr[s2];
            s2++;
            index++;
        }
        else if(arr[s1][i] == '\0' && arr[s2][j] == '\0')//if two strings are equivalent
        {
            tem[index] = arr[s1];
            index++;
            s1++;
            tem[index] = arr[s2]; 
            index++;
            s2++;
        }
    }

    for(k; k <= e2; k++) //copy the temporarily stored array to array that we want to sort
        arr[k] = tem[k];
}

void merge_sort(char * arr[], int start, int end)
{
    if(start < end)
    {
        int mid = (start + end) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, mid + 1, end);
    }
} 

And this is my 2D-array

input[2][3];

I use "strcpy" to copy "foo" and "bar" to input[1] and input[2], and set input[0][3] and input[1][3] to '\0'

This is how I call the function:

 void merge_sort(input, 0, 1);

I think the problem might be the first parameter of the function "merge" since I'm not sure if I can pass the 2D-array as "char * []"...

Thanks!

Answer 1

First, this is not a 2D array of strings. It's a 2D array of chars and 1D array of strings.

Second, you don't really need to write your own code for comparing strings since it is already written for you and ready to use, thanks to the developers of strcmp! Execute man strcmp in the terminal for more information about this great function!

Lastly, you have logical errors in your merging step. Here is some pseudocode for the merging step

merged[TOTAL_SIZE] // left + right sizes

int currIndex = 0 
leftIndex = the initial left index,
rightIndex = the initial right index;

for (i = 0, as i < TOTAL_SIZE, i++)
{
    if (leftIndex && rightIndex are within range)
    {
        if (arr[leftIndex] < arr[rightIndex])
        {
            merged[index++] = arr[leftIndex++]
        }
        else
        {
            merged[index++] = arr[rightIndex++]
        }
    }
    // if no more elements in the left half
    else if (leftIndex is out of bounds)
    {
            merged[index++] = arr[rightIndex++]
    }
    // if no more elements in the right half
    else
    {
            merged[index++] = arr[leftIndex++]
    }
}

PS: I didn't test the pseudocode above, so pardon me if there are any flaws.