# Merge Sort Algorithm
###### Sorting algorithm explained by @ivorchu

Merge sort algorithm is one of the most efficient sorting algorithms that work on a random distribution of data. It uses the idea of Divide and Conquer. Merge sort repeatedly breaks down lists of data into sublists until each sublist consists of a single element and then merging each other resulting in a sorted list. This allows the sorting process to exceed a time complexity of O(nlogn) maximum.

What is Divide and Conquer?
---
Merge sort applies the principles of Divide and Conquer, which is a common algorithm used while dealing with complex problems. Divide and Conquer simply works by recursively breaking down a problem into multiple sub-problems of the same or somehow related. The process continues until each sub-problem is simple enough to solve directly. Merge sort applies such method by simply split the data in half and combine recursively.

##### Below is an image of how Divide and Conquer was done

Steps On How Merge Sort Works
---
1. Divide the list recursively into half until each list is the size of one.
2. Compare the first element of each sublist, insert the smaller element to the new list.
3. Compare the greater element from the previous step with the second element of the other list, repeat the steps until one list is empty.
4. Insert the remaining elements if exist with their current order to the merged list.
5. Repeat the steps until there are no more sublists and the list is sorted.

> Note that each sublist is in order, so there is no need to compare every element in the sublist with every inserted element in the merged list.

##### Below is an image of how Merge Sort was done

Steps on Implementation (C++)
---
To begin with, create a function that divides the original list in half recursively. In here we find the division point (middle) and divide the list in the ***combine*** function (divide & merge) afterwards.

void Merge_Sort(int A[], int min, int max) {
    if (min < max) {
        int mid = (min + max) / 2;    // Find the middle of the list
        Merge_Sort(A, min, mid);    // Divide the first half
        Merge_Sort(A, mid + 1, max);    // Divide the second half
        combine(A, min, max, mid);    // Merge the sublists
    }
}

Create a function that divides and merges the sublists recursively. In here we set up the variable we need for this action.

void combine(int A[], int min, int max, int mid) {
    int leftLen = mid - min + 1;    // Length of the left sublist
    int rightLen = max - mid;    // Length of the right sublist
    int* left = new int[leftLen];    // Left subset
    int* right = new int[rightLen];    // Right subset
}

Fill in the divided subsets. (division)

for (int i = 0; i < leftLen; i++)
    left[i] = A[min + i];    // Insert into the left sublist
    
for (int i = 0; i < rightLen; i++)
    right[i] = A[i + mid + 1];    // Insert into the right sublist

Remember to include 2147483647 in the end of each subsets. This technique excludes the error occurs when the comparison function tries to find *A[length]* however the sublist ends in *A[length-1]* (data starts with index 0).
> 2147483647 = 2^31-1 is the maximum value of an *int*

left[leftLen] = 2147483647;
right[rightLen] = 2147483647;

Compare each value in the sublists. Insert the smaller value into the merged list. Keep comparing the greater value with the next value of the other sublist.

for (int k = min, i = 0, j = 0; k <= max; k++) {
    if (left[i] <= right[j]) {    // Comparison
        A[k] = left[i];    // Insert the smaller value
        i++;
    }
    else
    {
        A[k] = right[j];    // Insert the smaller value
        j++;
    }
}

### Complete Code

#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e5+5;

void combine(int A[], int min, int max, int mid) {
    int leftLen = mid - min + 1;
    int rightLen = max - mid;
    int* left = new int[leftLen];
    int* right = new int[rightLen];

    for (int i = 0; i < leftLen; i++)
        left[i] = A[min + i];
    
    for (int i = 0; i < rightLen; i++)
        right[i] = A[i + mid + 1];
    
    left[leftLen] = 2147483647;
    right[rightLen] = 2147483647;
    
    for (int k = min, i = 0, j = 0; k <= max; k++) {
        if (left[i] <= right[j]) {
            A[k] = left[i];
            i++;
        }
        else
        {
            A[k] = right[j];
            j++;
        }
    }
}

void Merge_Sort(int A[], int min, int max) {
    if (min < max) {
        int mid = (min + max) / 2;
        Merge_Sort(A, min, mid);
        Merge_Sort(A, mid + 1, max);
        combine(A, min, max, mid);
    }
}

int main() {
    int len;
    int A[MAXn];
    scanf("%d", &len);
    
    for (int i = 0; i < len; i++)
        scanf("%d", &A[i]);
    
    Merge_Sort(A, 0, len-1);
    
    for (int i = 0; i < len; i++) {
        printf("%d", A[i]);
    }
    return 0;
}

Download the code on Github!
https://github.com/Ivorchu/Merge-Sort-Explained.git