# Try to sort strings with merge sort

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

e.g.

``````arr = "foo";
arr = "bar";
``````

and I hope it to be like

``````arr = "bar";
arr = "foo";
``````

after being sorted but it doesn't work

Need some help here.

The following is my code for merge sort:

``````char * tem; // 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;
``````

I use "strcpy" to copy "foo" and "bar" to input and input, and set input and input 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!

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.