Tuesday, 12 September 2017

Merge Sorting is a sorting algorithm that uses the divide, conquer and combine algorithmic paradigm.

The most common algorithm used in external sorting is the merge sort. Merging is the process of combining two or more sorted files into the third sorted file. We can use a technique of merging two sorted lists. Divide and conquer is a general algorithm design paradigm that is used for merge sort. Merge sort have three steps to sort an input sequence A with n elements.   
Divide means partitioning the n-element array to be sorted into two sub arrays of n/2 elements. If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2 each containing about half of the elements of A. 
Conquer means sorting the two sub-arrays recursively using merge sort. 
Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.

Let us implement the merge technique for two sorted arrays. Let us write a merge function which accepts two sorted arrays A1 and A2 which containing elements n/2, respectively and merge them into a third array C containing n elements. Here, the array A1 is from low to mid, array A2 is from (mid +1) to high. 
   
Implementation of Merge Sorting using C++.
#include <iostream>
using namespace std;
// MS() function is used to merge two different sub-array which is already sorted in third array  
int MS(int arr[],int p,int mid,int r)
{
    int i,j,k;
    int n1=mid-p+1;
    int n2=r-mid;
    int L[n1],R[n2];
    for (i = 0; i < n1; i++)
    {
        L[i] = arr[p+ i];
    }
    for (j = 0; j < n2; j++)
    {
        R[j] = arr[mid + 1+ j];
    }
    i=0;
    j=0;
    k=p;
     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++;
    }
}
// mergeSort() is divide into equal parts and then call merge procedure 
void mergeSort(int arr[],int p,int r)
{
    if(p<r)
    {
        int mid=(p+r)/2;
        mergeSort(arr,p,mid);
        mergeSort(arr,mid+1,r);
        MS(arr,p,mid,r);
    }
}
// implementation of main function with different function calls.
int main() 
{
 int arr[100];
 for(int i=0;i<10;i++)
 {
     cin>>arr[i];
 }
 mergeSort(arr,0,9);
 cout<<"Sorted array is ";
 for(int i=0;i<10;i++)
    cout<<arr[i]<<" ";
}


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput