# 2. Merge Sort in C++

This section explains how the "divide and conquer" strategy of Merge Sort is implemented in C++. The logic is split into two primary functions: `mergeSort()` which handles the recursive division, and `merge()` which handles the conquering and sorting.

### The C++ Code Implementation

Here is the complete code for a Merge Sort implementation using `std::vector`.

```cpp
#include <iostream>
#include <vector>

// Utility function to print a vector
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// Merges two sorted subarrays into a single sorted subarray.
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Calculate sizes of the two temporary subarrays
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary vectors to hold the data
    std::vector<int> L(n1), R(n2);

    // Copy data from the main array to the temporary vectors
    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 the temporary vectors back into the original array arr[left..right]
    int i = 0; // Initial index for left subarray
    int j = 0; // Initial index for right subarray
    int k = left; // Initial index for the 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 any remaining elements from the left subarray
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy any remaining elements from the right subarray
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// The main recursive function that implements the "divide" phase
void mergeSort(std::vector<int>& arr, int left, int right) {
    // Base case: if the array has 1 or 0 elements, it's already sorted
    if (left >= right) {
        return;
    }

    // Find the middle point to divide the array
    int mid = left + (right - left) / 2;

    // Recursively call mergeSort for the two halves
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Merge the two now-sorted halves
    merge(arr, left, mid, right);
}

// Main driver function
int main() {
    std::vector<int> data = {6, 5, 3, 1, 8, 7, 2, 4};
    std::cout << "Original array: ";
    printVector(data);

    mergeSort(data, 0, data.size() - 1);

    std::cout << "Sorted array:   ";
    printVector(data);

    return 0;
}
```
### Output
```
Original array: 6 5 3 1 8 7 2 4 
Sorted array:   1 2 3 4 5 6 7 8 
```
### Code Breakdown
---
### Code Breakdown

#### The `mergeSort()` Function: The Divider
This function is the engine that drives the **"Divide"** phase.
1.  **Base Case**: The recursion stops when `left >= right`, which means the sub-array has one or zero elements and is considered sorted.
2.  **Divide**: It calculates the `mid` point of the current array segment. The formula `left + (right - left) / 2` is used to prevent potential overflow on very large arrays.
3.  **Recurse**: It calls itself for the left half (`left` to `mid`) and then for the right half (`mid + 1` to `right`).
4.  **Conquer**: After the recursive calls return (guaranteeing the two halves are sorted), it calls `merge()` to combine them into a single, sorted segment.

#### The `merge()` Function: The Conqueror
This function is the core of the algorithm where the actual sorting happens. It takes two adjacent, sorted sub-arrays and merges them.
1.  **Setup**: It creates two temporary vectors, `L` and `R`, and copies the data from the two halves of the main array into them.
2.  **Merge Loop**: It uses three index pointers: `i` for vector `L`, `j` for vector `R`, and `k` for the original array `arr`. It compares the elements at `L[i]` and `R[j]` and places the smaller of the two into `arr[k]`. It then increments the pointer of the vector from which the element was taken, as well as the pointer `k`.
3.  **Copy Leftovers**: After the main loop, one of the temporary vectors might still contain elements. The final two `while` loops copy these remaining elements back into the main array, ensuring all data is merged correctly.