🌟 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. Conquer- Recursively sort the left and right halves.

3. Combine-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:

[38, 27, 43, 3, 9, 82, 10]

We start by dividing it into two halves:

Left:  [38, 27, 43, 3]

Right: [9, 82, 10]

🔹 Step 3: Divide Left Half [38, 27, 43, 3]

[38, 27]   and   [43, 3]

Now divide again:

[38] [27]  and  [43] [3]

Merge and sort each pair:

[38] + [27] → [27, 38]

[43] + [3]  → [3, 43]

Now merge these two sorted subarrays:

[27, 38] + [3, 43] → [3, 27, 38, 43]

✅ Left half sorted: [3, 27, 38, 43]

🔹 Step 4: Divide Right Half [9, 82, 10]

[9] and [82, 10]

Split [82, 10]:

[82] [10] → merge → [10, 82]

Now merge with [9]:

[9] + [10, 82] → [9, 10, 82]

✅ Right half sorted: [9, 10, 82]

🔹 Step 5: Final Merge

Now merge the two sorted halves:

Left:  [3, 27, 38, 43]

Right: [9, 10, 82]

📚 Example:merge

Left:  [3, 27, 38, 43]

Right: [9, 10, 82]

Merge process:

Step     Left Element Right Element     Result

1         3          <                    9         → [3]

2         27         >                   9         → [3, 9]

3         27         >                 10         → [3, 9, 10]

4         27         <                 82         → [3, 9, 10, 27]

5         38         <                 82         → [3, 9, 10, 27, 38]

6         43         <                 82         → [3, 9, 10, 27, 38, 43]

7 (Left exhausted) + [82]         → [3, 9, 10, 27, 38, 43, 82]

Explanation

1. Divide phase (top-down):

   • The array is split recursively until each subarray has only one element.

2. Conquer phase (bottom-up):

   • Adjacent subarrays are merged in sorted order.

3. Final result:

• The sorted array is built step by step through merging.

Merge Sort Tree Visualization

                           [38, 27, 43, 3, 9, 82, 10]
                                    /           \
                     [38, 27, 43, 3]             [9, 82, 10]
                      /           \               /       \
                [38, 27]        [43, 3]        [9]      [82, 10]
                 /    \          /   \                   /    \
             [38]   [27]     [43]  [3]              [82]    [10]

                 ↓ Merge           ↓ Merge               ↓ Merge
               [27, 38]          [3, 43]               [10, 82]

                      ↓ Merge Left Half        ↓ Merge Right Half
                                                [9, 10, 82]
              [3, 27, 38, 43]
                                 ↓ Final Merge
                         [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).

---

📋  Merge sort :Pseudo code

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