Merge Sort

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // Create temporary arrays
    int L[n1], R[n2];
    
    // Copy data to temp arrays
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    // Merge temp arrays back
    int 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++;
    }
    
    // Copy remaining elements
    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 mid = left + (right - left) / 2;
        
        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // Merge sorted halves
        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

This program teaches you how to implement the Merge Sort algorithm in C++. Merge Sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the sorted halves. It's one of the most efficient sorting algorithms with guaranteed O(n log n) performance, making it ideal for large datasets.

---

1. What This Program Does

The program sorts an array of integers using the Merge Sort algorithm. For example:

• Input array: [64, 34, 25, 12, 22, 11, 90]
• Output array: [11, 12, 22, 25, 34, 64, 90]

Merge Sort uses a divide-and-conquer approach: it divides the problem into smaller subproblems, solves them recursively, and combines the solutions.

---

2. Header File Used

#include <iostream>

This header provides:

• cout for displaying output
• cin for taking input from the user

---

3. Understanding Merge Sort

Divide-and-Conquer Strategy:

1. Divide: Split array into two halves

2. Conquer: Recursively sort both halves

3. Combine: Merge the sorted halves

Visual Example:

[64, 34, 25, 12, 22, 11, 90] ↓ Divide [64, 34, 25] [12, 22, 11, 90] ↓ Divide ↓ Divide [64] [34, 25] [12, 22] [11, 90] ↓ Merge ↓ Merge ↓ Merge [64] [25, 34] [12, 22] [11, 90] ↓ Merge ↓ Merge [25, 34, 64] [11, 12, 22, 90] ↓ Merge [11, 12, 22, 25, 34, 64, 90]

---

4. Function: merge()

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

int L[n1], R[n2];

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

// Merge temp arrays back
int 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++;
}

// Copy remaining elements
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];

}

How it works:

• Creates temporary arrays L and R for left and right halves
• Copies elements to temp arrays
• Merges by comparing elements from both arrays
• Copies remaining elements from non-empty array

---

5. Function: mergeSort()

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);
}

}

How it works:

• Base case: if left >= right, subarray has 0 or 1 element (already sorted)
• Divide: calculate mid point
• Conquer: recursively sort left and right halves
• Combine: merge the sorted halves

---

6. Understanding the Merge Process

Merging Two Sorted Arrays:

Left: [25, 34, 64] Right: [11, 12, 22, 90]

Step 1: Compare 25 and 11 → 11 is smaller → place 11

Result: [11, ...]

Step 2: Compare 25 and 12 → 12 is smaller → place 12

Result: [11, 12, ...]

Step 3: Compare 25 and 22 → 22 is smaller → place 22

Result: [11, 12, 22, ...]

Step 4: Compare 25 and 90 → 25 is smaller → place 25

Result: [11, 12, 22, 25, ...]

Step 5: Compare 34 and 90 → 34 is smaller → place 34

Result: [11, 12, 22, 25, 34, ...]

Step 6: Compare 64 and 90 → 64 is smaller → place 64

Result: [11, 12, 22, 25, 34, 64, ...]

Step 7: Right array exhausted, copy remaining from left

Result: [11, 12, 22, 25, 34, 64, 90]

---

7. Time and Space Complexity

Time Complexity: O(n log n) in all cases

• Divide: O(log n) levels of recursion
• Merge: O(n) work at each level
• Total: O(n log n) - consistent performance

Space Complexity: O(n)

• Requires temporary arrays for merging
• Additional space for recursive calls: O(log n)
• Total: O(n)

Stability: Stable

• Merge process preserves relative order
• When L[i] == R[j], L[i] is placed first (<= comparison)

---

8. When to Use Merge Sort

Best For:

• Large datasets
• When stable sorting is required
• When consistent O(n log n) performance is needed
• External sorting (sorting data that doesn't fit in memory)
• Linked lists (efficient merge operation)

Not Recommended For:

• Small datasets (overhead of recursion and merging)
• When memory is limited (requires O(n) extra space)
• When in-place sorting is required

---

9. Important Considerations

Recursive Nature:

• Uses recursion to divide problem
• Base case: subarray with 0 or 1 element
• Each recursive call handles smaller subproblem

Temporary Arrays:

• Requires O(n) extra space
• L and R arrays store halves during merge
• Space trade-off for guaranteed performance

Mid Calculation:

• mid = left + (right - left) / 2
• Prevents integer overflow
• Better than (left + right) / 2

---

10. return 0;

This ends the program successfully.

---

Summary

• Merge Sort uses divide-and-conquer: divide, conquer (recursively sort), combine (merge).
• Time complexity: O(n log n) in all cases - consistent and reliable.
• Space complexity: O(n) - requires temporary arrays for merging.
• Stable algorithm - preserves relative order of equal elements.
• Guaranteed O(n log n) performance makes it reliable for large datasets.
• Recursive algorithm - divides problem into smaller subproblems.
• Merge process combines two sorted arrays efficiently.
• Understanding Merge Sort is essential for learning efficient sorting algorithms.

This program is fundamental for beginners learning divide-and-conquer algorithms, understanding recursion, and preparing for advanced algorithm design in C++ programs.