Data structures quick Sorting

Merge Sorting notes By Shanth…

# Merge Sort: Detailed Explanation and Example Programs

## Overview
Merge sort is a classic divide-and-conquer sorting algorithm known for its efficiency and stability.
It works by recursively dividing the array into smaller subarrays until each subarray contains
only one element, then merging these subarrays back together in a sorted order.

### Steps of Merge Sort:
1. **Divide**: Recursively divide the array into two halves until each subarray contains only one
element.
2. **Conquer**: Sort each subarray.
3. **Merge**: Merge the sorted subarrays back together to form the final sorted array.

### Example:
Let's sort the array `[38, 27, 43, 10]` using merge sort:

1. **Divide**:
- `[38, 27, 43, 10]` is divided into `[38, 27]` and `[43, 10]`.
- Further division: `[38]` and `[27]`, `[43]` and `[10]`.

2. **Conquer**:
- All single-element subarrays are considered sorted.

3. **Merge**:
- Merge `[38]` and `[27]` to get `[27, 38]`.
- Merge `[43]` and `[10]` to get `[10, 43]`.
- Finally, merge `[27, 38]` and `[10, 43]` to obtain the sorted array `[10, 27, 38, 43]`.

Thus, the sorted array is `[10, 27, 38, 43]`.

---

## Merge Sort Implementation in C++

```cpp
#include <iostream>
using namespace std;

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

, int L[n1], R[n2];

for (int i = 0; i < n1; i++)
L[i] = array[left + i];
for (int j = 0; j < n2; j++)
R[j] = array[mid + 1 + j];

int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
array[k] = L[i];
i++;
} else {
array[k] = R[j];
j++;
}
k++;
}

while (i < n1) {
array[k] = L[i];
i++;
k++;
}

while (j < n2) {
array[k] = R[j];
j++;
k++;
}
}

void mergeSort(int array[], int const begin, int const end) {
if (begin >= end)
return;

int mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

int main() {
int arr[] = {38, 27, 43, 10};