Merge Sorting.

// Assignment Name : Merge Sort [Implementation in C or CPP]
// Time Complexity : O(n log (n))
// *Compiler : "Microsoft Visual Studio"
// AUTHOR : Fueanta
// Date : Oct 15, 2016

#include "cstdio"
#define MAX 100

void Merge(int *, int, int, int);
void MergeSort(int *, int, int);

void main() {
    int arr[MAX]; int size;
    printf("Array size : "); scanf_s("%d", &size);
    printf("\nGive the array elements...\n\n");
    for (int i = 0; i < size; i++) {
        printf("Element %d : ", i + 1);
        scanf_s("%d", &arr[i]);
    }
    printf("\nGiven array without sorting:\n\n");
    for (int i = 0; i < size; i++)
        printf("|%d| ", arr[i]);
    MergeSort(arr, 0, size - 1);
    printf("\n\nGiven array after merge sorting:\n\n");
    for (int i = 0; i < size; i++)
        printf("|%d| ", arr[i]);
    printf("\n\n");
}

void MergeSort(int arr[], int first, int last) {
    if (first < last) {
        int MID = (first + last) / 2;
        MergeSort(arr, first, MID);
        MergeSort(arr, MID + 1, last);
        Merge(arr, first, MID, last);
    }
}

void Merge(int arr[], int first, int MID, int last) {
    int i1, j1; i1 = j1 = first;
    int i2 = MID + 1, demo[MAX];
    while (i1 <= MID && i2 <= last) {
        if (arr[i1] <= arr[i2])
            demo[j1++] = arr[i1++];
        else demo[j1++] = arr[i2++];
    }
    while (i1 <= MID) demo[j1++] = arr[i1++];
    while (i2 <= last) demo[j1++] = arr[i2++];
    for (int i = first; i <= last; i++) {
        arr[i] = demo[i];
    }
}