3.C Program to sort the given list using merge sort technique(Part B)

3.C Program to sort the given list using merge sort technique

ALGORITHM :

Step 1: Start

Step 2: Implement the merge function that takes the list (my_list), left index (left), mid index (mid), and right index (right) as parameters.

Step 3: Create two temporary arrays (left_array and right_array) to hold the elements from the left and right subarrays.

Step 4: Copy the elements from my_list to left_array (from left to mid) and right_array (from mid+1 to right).

Step 5: Merge the two arrays (left_array and right_array) back into my_list in a sorted order.

Step 6: Implement the merge_sort function that takes the list (my_list), left index (left), and right index (right) as parameters.

Step 7: If left is less than right:

        a. Calculate mid as (left + right) / 2.

        b. Recursively call merge_sort for the left half (my_list, left, mid).

        c. Recursively call merge_sort for the right half (my_list, mid + 1, right).

        d. Call merge function to merge the left and right halves in sorted order.

Step 8: Input the number of elements (n) and the list of elements (my_list).

Step 9: Call merge_sort(my_list, 0, n-1) to sort the list.

Step 10: Display the sorted list.

Step 11: End

SOURCE CODE :

#include <stdio.h>

void merge(int arr[], int left, int middle, int right) {

    int i, j, k;

    int n1 = middle - left + 1;

    int n2 = right - middle;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[middle + 1 + j];

    i = 0;

    j = 0;

    k = left;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int middle = left + (right - left) / 2;

        mergeSort(arr, left, middle);

        mergeSort(arr, middle + 1, right);

        merge(arr, left, middle, right);

    }

}

int main() {

    int n;

    printf("Enter the number of elements in the list: ");

    scanf("%d", &n);

    int arr[n];

    printf("Enter %d elements: ", n);

    for (int i = 0; i < n; i++) {

        scanf("%d", &arr[i]);

    }

    mergeSort(arr, 0, n - 1);

    printf("Sorted list: ");

    for (int i = 0; i < n; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    return 0;

}

OUTPUT 

Enter the number of elements in the list: 7

Enter 7 elements: 19 7 12 3 8 15 5

Sorted list: 3 5 7 8 12 15 19