**Implementation of Merge Sort algorithm in C++ language**

*This particular algorithm is also depend upon the divide and conquer technique.Its design paradigm is based on multi-branched recursion. It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.*

*Program Code:**#include<iostream>*

*using namespace std;*

*// function definition which is going to merge or combine the solved sub-problem*

*void merge(int arr[], int l, int m, int r)*

*{*

*int i, j, k;*

*int n1 = m - l + 1;*

*int n2 = r - m;*

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

*for (i = 0; i < n1; i++)*

*L[i] = arr[l + i];*

*for (j = 0; j < n2; j++)*

*R[j] = arr[m + 1+ j];*

*i = 0;*

*j = 0;*

*k = l;*

*while (i < n1 && j < n2)*

*{*

*if (L[i] <= R[j])*

*{*

*arr[k] = L[i];*

*i++;*

*}*

*else*

*{*

*arr[k] = R[j];*

*j++;*

*}*

*k++;*

*}*

*while (i < n1)*

*{*

*arr[k] = L[i];*

*i++;*

*k++;*

*}*

*while (j < n2)*

*{*

*arr[k] = R[j];*

*j++;*

*k++;*

*}*

*}*

*// this function is divide the problem into sub-problems equally recursively*

*void mergeSort(int arr[], int l, int r)*

*{*

*if (l < r)*

*{*

*int m = l+(r-l)/2;*

*mergeSort(arr, l, m);*

*mergeSort(arr, m+1, r);*

*merge(arr, l, m, r);*

*}*

*}*

*// this function display the array elements*

*void printArray(int A[], int size)*

*{*

*int i;*

*for (i=0; i < size; i++)*

*cout<< A[i]<<"\t";*

*cout<<endl;*

*}*

*// main() function with different function calls*

*int main()*

*{*

*int arr[] = {12, 11, 13, 5, 6, 7, 2, 3, 8, 9, 18, 20};*

*int arr_size = sizeof(arr)/sizeof(arr[0]);*

*cout<<"*

*The given array for sorting is :*

*"<<endl;*

*printArray(arr, arr_size);*

*mergeSort(arr, 0, arr_size - 1);*

*cout<<"*

*After applying merge sort the above array is:*

*"<<endl;*

*printArray(arr, arr_size);*

*return 0;*

*}*

*The program output is tested on www.jdoodle.com*

*Output:**The given array for sorting is :*

*12 11 13 5 6 7 2 3 8 9 18 20*

*After applying merge sort the above array is:*

*2 3 5 6 7 8 9 11 12 13 18 20*

*Thanks*

*Mukesh Rajput*

## No comments:

## Post a Comment

Thanks

Mukesh Rajput