Merge Sort: Algorithm & Implementation

1️⃣ What is Merge Sort?

🔹 Merge Sort is a divide-and-conquer sorting algorithm.
🔹 It recursively splits the array into halves, sorts them, and then merges the sorted halves back together.
🔹 Stable sorting algorithm (preserves the order of equal elements).

✅ Time Complexity

Case	Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

✅ Space Complexity

• O(n) (extra space for merging)

✅ Is it Stable?

✔ Yes (Preserves order of equal elements)

---

2️⃣ How Merge Sort Works

🔹 Divide: Split the array into two halves.
🔹 Conquer: Recursively sort both halves.
🔹 Combine: Merge the sorted halves back together.

Step-by-Step Example

📝 Input: [38, 27, 43, 3, 9, 82, 10]

Step	Left Half	Right Half	Merging Process
1	[38, 27, 43]	[3, 9, 82, 10]	Divide into halves
2	[38] [27, 43]	[3, 9] [82, 10]	Further divide
3	[38] [27] [43]	[3] [9] [82] [10]	Base case reached
4	[27, 38, 43]	[3, 9, 10, 82]	Merge sorted subarrays
5	[3, 9, 10, 27, 38, 43, 82]	Final sorted array

🔹 Final Sorted Array: [3, 9, 10, 27, 38, 43, 82]

---

3️⃣ Merge Sort Algorithm

🔹 Pseudocode

MergeSort(arr, left, right):
    if left < right:
        mid = (left + right) / 2
        MergeSort(arr, left, mid)
        MergeSort(arr, mid + 1, right)
        Merge(arr, left, mid, right)

Merge(arr, left, mid, right):
    Create left and right subarrays
    Compare elements and merge them in sorted order

---

4️⃣ Merge Sort Implementation in C

#include <stdio.h>

// Function to merge two halves
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int leftArr[n1], rightArr[n2];

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

    int i = 0, j = 0, k = left;

    // Merge the temp arrays back
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// Function to perform Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

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

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

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

🔹 Output

Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Guaranteed O(n log n) performance (better than Quick Sort in worst case).
✔ Stable sorting algorithm (preserves order of equal elements).
✔ Efficient for large datasets and linked lists.

❌ Disadvantages

❌ Requires O(n) extra space (not in-place sorting).
❌ Slower than Quick Sort for small datasets due to recursion overhead.
❌ More memory-consuming compared to in-place sorting algorithms.

---

6️⃣ When to Use Merge Sort?

🔹 Best for sorting large datasets (better than Quick Sort in worst case).
🔹 Useful when stable sorting is required (preserves order of duplicate elements).
🔹 Preferred for linked lists (avoids excessive swaps).
🔹 Not ideal when memory is limited (since it uses extra space).

💡 For best performance, use Merge Sort for large, linked, or stable sorts! 🚀