C++ Program For Merge Sort

 Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Program:

#include <iostream>
using namespace std;

void merge(int arr[],int l,int mid,int r)   //merging two sorted arrays
{
    int n1 = mid - l + 1;
    int n2 = r - mid;

    //temporaries arrays
    int a [n1];  //left array
    int b [n2]; //right array

    for(int i = 0; i < n1; i++)
    {
        a[i]=arr[l + i];
    }

    for(int i = 0; i < n2; i++)
    {
        b[i]=arr[mid+1+i];
    }

    int i = 0, j = 0, k = l;

    //finding smaller elements from two temporaries arrays
    //and storing it in original array
    while(i < n1 && j < n2)
    {
        if(a[i] < b[j])
        {
            arr[k] = a[i];
            i++;
            k++;
        }
        else
        {
            arr[k] = b[j];
            j++;
            k++;
        }
    }

    //if one of the temporaries array gets empty and another array is not empty
    //then store elements of another array to original array
    while(i < n1)
    {
        arr[k] = a[i];
        i++;
        k++;
    }
    while(j < n2)
    {
        arr[k] = b[j];
        j++;
        k++;
    }
}

//l is left most index and r is the right most index
//of array to be sorted
void mergeSort(int arr[],int l,int r)   
{
    if(l < r)
    {
        //mid is middle index of given array
        int mid = (l + r) / 2;

        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);


        merge(arr,l,mid,r);
    }
}
int main()
{
    int arr[] = {38,27,43,3,9,82,10};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array is:" << endl;
    for(int i = 0; i < n; i++)
    cout << arr[i] << " ";
    
    mergeSort(arr,0,n-1);
    
    cout << endl << "Sorted array is:" << endl;
    for(int i = 0; i < n; i++)
    cout << arr[i] << " ";

    return 0;
}

Output:

Original array is:
38 27 43 3 9 82 10 
Sorted array is:
3 9 10 27 38 43 82