merge sort for strings in c

Sure! Here is an example of how to implement merge sort for strings in C, along with explanations for each step:

#include <stdio.h>
#include <string.h>

void merge(char arr[][100], int low, int mid, int high) {
    int i, j, k;
    int n1 = mid - low + 1;
    int n2 = high - mid;

    char L[n1][100], R[n2][100];

    // Copy data to temporary arrays
    for (i = 0; i < n1; i++) {
        strcpy(L[i], arr[low + i]);
    }
    for (j = 0; j < n2; j++) {
        strcpy(R[j], arr[mid + 1 + j]);
    }

    // Merge the temporary arrays back into arr[]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = low; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (strcmp(L[i], R[j]) <= 0) {
            strcpy(arr[k], L[i]);
            i++;
        }
        else {
            strcpy(arr[k], R[j]);
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        strcpy(arr[k], L[i]);
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        strcpy(arr[k], R[j]);
        j++;
        k++;
    }
}

void mergeSort(char arr[][100], int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;

        // Sort first and second halves
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);

        // Merge the sorted halves
        merge(arr, low, mid, high);
    }
}

int main() {
    char arr[][100] = {"banana", "apple", "cherry", "date", "grape"};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }

    mergeSort(arr, 0, n - 1);

    printf("\nAfter sorting:\n");
    for (int i = 0; i < n; i++) {
        printf("%s ", arr[i]);
    }

    return 0;
}

Explanation:

The merge function is defined to merge two sorted subarrays into one sorted array. It takes the array arr, the indices low, mid, and high, and performs the merging operation.
Inside the merge function, two temporary arrays L and R are created to store the subarrays to be merged. The sizes of these arrays are calculated using the indices.
The data from the original array arr is copied into the temporary arrays L and R using the strcpy function.
The merging of the temporary arrays L and R is performed in a while loop. The elements are compared and copied back into the original array arr in sorted order using the strcmp and strcpy functions.
After the while loop, any remaining elements in L or R are copied back into the original array arr.
The mergeSort function is defined to recursively divide the array into smaller subarrays until there is only one element in each subarray.
The mergeSort function calls itself to sort the first and second halves of the array.
After the recursive calls, the merge function is called to merge the sorted halves back into the original array.
Finally, the main function initializes an array of strings, calls the mergeSort function to sort the array, and prints the sorted array.

This implementation of merge sort for strings in C follows the standard divide-and-conquer approach, where the array is recursively divided into smaller subarrays until the base case is reached. The merging of the subarrays is done by comparing and copying elements in a sorted manner.