🌟 Merge Sort

Merge Sort is a Divide and Conquer algorithm.

• It divides the array into two halves,

• Sorts each half recursively,

• And then merges the two sorted halves into one sorted array.

Main idea:
👉 Break the problem into smaller pieces, solve them individually, then combine the solutions.

---

📜 Merge Sort Algorithm:

1. Divide the array into two halves.

2. Recursively sort the left and right halves.

3. Merge the sorted halves.

---

Algorithm Steps

MergeSort(A, left, right):

1. If left >= right, return (base case: array of 1 element is already sorted)

2. Find the middle point mid = (left + right)/2

3. Call MergeSort(A, left, mid)

4. Call MergeSort(A, mid+1, right)

5. Call Merge(A, left, mid, right)

---

Merge(A, left, mid, right):

1. Create two temporary arrays:

   • Left half → A[left...mid]

   • Right half → A[mid+1...right]

2. Compare elements of two arrays one by one, and copy the smaller one into the original array.

3. Copy any remaining elements.

---

📚 Example:

Suppose the array is: [38, 27, 43, 3, 9, 82, 10]

1. Split → [38, 27, 43, 3] and [9, 82, 10]

2. Split further → [38, 27] and [43, 3]

3. Split → [38] and [27] (single element, sorted)

4. Merge → [27, 38]

5. Split [43] and [3], Merge → [3, 43]

6. Merge → [27, 38, 3, 43] → after sorting → [3, 27, 38, 43]

7. Similarly for [9, 82, 10] → merge sorted → [9, 10, 82]

8. Finally merge → [3, 9, 10, 27, 38, 43, 82]

Sorted array: [3, 9, 10, 27, 38, 43, 82]

---

🧠 Important Points

• Time complexity: O(n log n) in all cases (best, average, worst).

• Space complexity: O(n) extra space needed (for temporary arrays).

• Merge Sort is Stable and efficient for large data sets (does not change the order of equal elements).

---

📋  Algorithm:

Algorithm MergeSort(A, left, right)
    if left < right
        mid = (left + right)/2
        MergeSort(A, left, mid)
        MergeSort(A, mid+1, right)
        Merge(A, left, mid, right)

Algorithm Merge(A, left, mid, right)
    Create temporary arrays L[] and R[]
    Copy data to L[] and R[]
    i = 0, j = 0, k = left
    while i < size of L and j < size of R
        if L[i] <= R[j]
            A[k] = L[i]
            i++
        else
            A[k] = R[j]
            j++
        k++
    Copy remaining elements of L[] (if any)
    Copy remaining elements of R[] (if any)

 C Program Merge Sort:
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

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

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

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

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Same as (left+right)/2 but avoids overflow

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void readArray(int arr[], int n) {
    for (int i=0; i<n; i++)
        scanf("%d", &arr[i]);
    
}
int main() {
    int arr[50] ;
    int n;
    
    printf("Enter the number of elements \n");
    scanf("%d",&n);
    printf("Enter the array elements\n");
    readArray(arr,n);
    
    printf("Original array: ");
    printArray(arr, n);

    mergeSort(arr,0,n-1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output
Enter the number of elements 
6
Enter the array elements
9 5 3 8 1 2
Original array: 9 5 3 8 1 2 
Sorted array: 1 2 3 5 8 9