Merge Sort is a classic, efficient, and stable comparisonbased sorting algorithm that follows the divideandconquer paradigm. The core idea of Merge Sort is to divide the input array into smaller subarrays, sort these subarrays, and then merge them back together to form a sorted array.
Merge Sort operates by recursively splitting the array into two halves until each subarray contains only one element (which is trivially sorted). After reaching this base case, the algorithm begins to merge the subarrays back together in a sorted order. Here’s how it works stepbystep:

Divide:
 The array is recursively divided into two halves. This is done by calculating the middle index (
mid
) of the current segment of the array. The left half is from the start index (left
) tomid
, and the right half is frommid + 1
to the end index (right
).
 The array is recursively divided into two halves. This is done by calculating the middle index (

Conquer (Sort):
 Once the array is divided into singleelement subarrays, the merge step starts. Each subarray is already sorted (since it contains only one element), so the merge process can begin.

Merge:
 The
merge
function is responsible for combining two sorted subarrays into a single sorted array. The process involves: Copying Subarrays: First, the left and right subarrays are copied into temporary vectors
a
andb
.  Merging: Two pointers (
i
andj
) are used to traverse thea
andb
vectors. The smaller of the two pointedto elements is appended to the result vectorres
. This continues until all elements from eithera
orb
have been added tores
.  Appending Remaining Elements: If one of the vectors still has remaining elements, they are directly appended to
res
since they are already sorted.  Copying Back: Finally, the sorted elements from
res
are copied back into the original array, replacing the original unsorted elements.
 Copying Subarrays: First, the left and right subarrays are copied into temporary vectors
 The
Code Explanation
void merge(vector<int> &arr, int left, int middle, int right) {
vector<int> a, b;
// Copy left half to a
for (int i = left; i <= middle; i++) {
a.push_back(arr[i]);
}
// Copy right half to b
for (int i = middle + 1; i <= right; i++) {
b.push_back(arr[i]);
}
int i = 0, j = 0;
vector<int> res;
// Merge the two halves back into res
while (i < a.size() && j < b.size()) {
if (a[i] < b[j]) {
res.push_back(a[i]);
i++;
} else {
res.push_back(b[j]);
j++;
}
}
// Add remaining elements from a
while (i < a.size()) {
res.push_back(a[i]);
i++;
}
// Add remaining elements from b
while (j < b.size()) {
res.push_back(b[j]);
j++;
}
// Copy the sorted result back into the original array
for (int k = 0; k < res.size(); k++) {
arr[left + k] = res[k];
}
}
void mergeSort(vector<int> &arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid); // Sort the left half
mergeSort(arr, mid + 1, right); // Sort the right half
merge(arr, left, mid, right); // Merge the sorted halves
}
}
How It Works
 Recursive Splitting: The
mergeSort
function splits the array into smaller and smaller subarrays by recursively calling itself until each subarray contains a single element.  Merging: The
merge
function then takes two sorted subarrays and merges them into a single sorted array. This is the critical step where the actual sorting happens.
Complexity Analysis

Time Complexity: The time complexity of Merge Sort is O(n log n), where
n
is the number of elements in the array. Then log n
arises because: The array is split
log n
times (since each split halves the array).  Each merge operation takes O(n) time to combine the elements.
 The array is split

Space Complexity: The space complexity is O(n) due to the additional space used by the temporary vectors
a
,b
, andres
. These vectors are necessary for storing the elements during the merging process.