Merge Sort (मर्ज सॉर्ट)

Merge Sort (मर्ज सॉर्ट):-

It is a general purpose and comparison based sorting method. it is also known as divide and conquer algorithm. In merge sort, first of all we divide the given list in to two parts and we obtain two sub-list. Now again we divide these two sub-list in to two parts and we obtain four sub-list.this process will continue until each list has only one element and we know that a list of one element is always sorted. After that we compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

यह एक जनरल पर्पस एवं तुलना पर आधारित सॉर्टिंग मेथड है। इसे डिवाइड एंड कॉन्कर अल्गोरिथम के नाम से भी जाना जाता है। इस मेथड में सर्वप्रथम दी गयी लिस्ट को दो भागो में विभाजित किया जाता है जिससे दो सबलिस्ट प्राप्त होती है, अब पुनः दोनों सबलिस्ट को दो भागो में विभाजित किया जाता है जिससे चार सबलिस्ट प्राप्त होती है। यह प्रक्रिया तब तक चलती रहती है जब तक की सभी सबलिस्ट में केवल एक एलिमेंट शेष ना रह जाये एवं हमे ज्ञात है कि एक एलिमेंट की लिस्ट सदैव सॉर्टेड होती है। 

अब प्रत्येक एलिमेंट को उसके नज़दीकी एलिमेंट से मैचकर सॉर्ट किया जाता है एवं दोनों लिस्ट को मर्ज किया जाता है। 

अंत में सभी एलेमेंट्स को सॉर्ट करके, सबलिस्ट को मर्ज करने पर परिणामी सॉर्टेड लिस्ट प्राप्त होती है।

Algoritm/Function/Program for Merge Sort:-

File Name:- msort.cpp

#include<iostream.h>

#include<conio.h>

#define N 10

int list[N];

int mergesort(int first,int last){

int m;

if(last>first){

m=(first+last)/2;

mergesort(first,m);

mergesort(m+1,last);

merge(first,m,m+1,last);

}

return 1;

}

int merge(int first1,int last1,int first2,int last2){

int i=first1,j=first2,

temp[N],k=0;

while(i<=last1&&j<=last2 ){

if(list[i]<list[j]){

temp[k]=list[i];

i++;k++;

}

else{

temp[k]=list[j];

j++;k++;

}

}

while(i<=last1){

temp[k]=list[i];

i++;k++;

}

while(j<=last2){

temp[k]=list[j];

j++;k++;

}

for(i=first1,k=0;i<=last2;i++,k++)

{

list[i]=temp[k];

}

return 1;

}

void main(){

int i;

clrscr();

cout<<"Merge Sort"<<endl<<"Enter elements of List"<<endl;

for(i=0;i<N;i++){

cout<<"Enter "<<i+1<<" element= ";

cin>>list[i];

}

cout<<"Before Sorting List is:- ";

for(i=0;i<N;i++){

cout<<list[i]<<" ";

}

mergesort(0,N-1);

cout<<endl<<"After Sorting List is:- ";

for(i=0;i<N;i++){

cout<<list[i]<<" ";

}

getch();

}

File Name:- msort.c

#include<stdio.h>

#include<conio.h>

#define N 10

int list[N];

int mergesort(int first,int last){

int m;

if(last>first){

m=(first+last)/2;

mergesort(first,m);

mergesort(m+1,last);

merge(first,m,m+1,last);

}

return 1;

}

int merge(int first1,int last1,int first2,int last2){

int i=first1,j=first2,

temp[N],k=0;

while(i<=last1&&j<=last2 ){

if(list[i]<list[j]){

temp[k]=list[i];

i++;k++;

}

else{

temp[k]=list[j];

j++;k++;

}

}

while(i<=last1){

temp[k]=list[i];

i++;k++;

}

while(j<=last2){

temp[k]=list[j];

j++;k++;

}

for(i=first1,k=0;i<=last2;i++,k++)

{

list[i]=temp[k];

}

return 1;

}

void main(){

int i;

clrscr();

printf("Merge Sort\nEnter elements of List\n");

for(i=0;i<N;i++){

printf("enter %d element=",i+1);

scanf("%d",&list[i]);

}

printf("Before Sorting list is-");

for(i=0;i<N;i++){

printf("%d ",list[i]);

}

mergesort(0,N-1);

printf("After Sorting  list is-");

for(i=0;i<N;i++){

printf("%d ",list[i]);

}

getch();

}