#### Sorting

Problem
Implement the Merge sort algorithm.

Solution
Merge sort is a divide & conquer algorithm which works by dividing the array of elements into sub-arrays, sorting the subarrays and then merging the sorted sub-arrays to produce final sorted array.
Consider an unsorted array of size n. First the unsorted array is divided into n sub-arrays ( each array of size 1 ) [ an array of size 1 is by default sorted ].
Merge the two adjacent sorted sub-arrays and repeat the steps of sorting & merging sub-arrays until only one sub-array remains and that is the final sorted array. Complexity of the algorithm is O(n log n).
Consider the following array { 7, 2, 5, 3, 1, 8, 4, 6 }. Let’s see how Merge sort technique works :-

{ 7 } | { 2 } | { 5 } | { 3 } | { 1 } | { 8 } | { 4 } | { 6 } ( Array is divided into 8 sub-arrays of size 1 )

First Merge :-
{ 2, 7 } | { 3, 5 } | { 1, 8 } | { 4, 6 } ( Merge the adjacent sorted sub-arrays of size 1 )

Second Merge :-
{ 2, 3, 5, 7 } | { 1, 4, 6, 8 } ( Merge the adjacent sorted sub-arrays of size 2 )

Third Merge :-
{ 1, 2, 3, 4, 5, 6, 7, 8 } ( Merge the adjacent sorted sub-arrays of size 4 )

Now, we have only one sub-array of size n, which is the final sorted array.

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

// Display the Array
void displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}

// merge 2 halves of arr[start_idx...mid_idx] and
// arr[mid_idx+1...start_idx] into arr[]
void merge(int arr[],int start_idx, int mid_idx, int end_idx) {
int i,j,k;
int size1 = mid_idx - start_idx + 1;
int size2 = end_idx - mid_idx;

// temporary arrays
int left[size1];
int right[size2];

// copy data from original array into temporay arrays
for (i=0;i<size1;i++) {
left[i] = arr[start_idx+i];
}
for (j=0;j<size2;j++) {
right[j] = arr[mid_idx+1+j];
}

// merge the temporary arrays back to original array
// s.t the original array becomes sorted
i = 0; j = 0; k = start_idx;
while (i < size1 &&  j < size2) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
}
else {
arr[k] = right[j];
j++;
}
k++;
}

// copy remaining elements of left[], if any
while (i < size1) {
arr[k] = left[i];
i++;
k++;
}

// copy remaining elements of right[], if any
while (j < size2) {
arr[k] = right[j];
j++;
k++;
}
}

// merge sort the array recursively
// divide and conquer
void mergeSort(int arr[], int start_idx, int end_idx) {
int mid_idx;
if (start_idx < end_idx) {
mid_idx = (start_idx + end_idx) / 2;
// mergesort the two halves of array first
mergeSort(arr, start_idx, mid_idx);
mergeSort(arr, mid_idx+1, end_idx);
// merge the two halves
// merged array is sorted
merge(arr,start_idx, mid_idx, end_idx);
}
}

// main
int main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
mergeSort(arr,0,size-1);
cout<<"\nSorted Array   :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}```