Merge Sort | One of the best sorting algorithms used for large inputs

Here, we are going to learn about the Merge Sort - one of the best sorting algorithms used for large inputs.
Submitted by Ankit Sood, on November 09, 2018

What is sorting?

Sorting allows us to process our data in a more organized and efficient way. It makes searching easy as it will now take less time to search for a specific value in a given sorted sequence with respect to a sequence which was initially unsorted.

In programming, there are any numbers of sorting algorithms, some of them are given below,

1. Bubble sort
2. Selection sort
3. Insertion sort
4. Merge sort
5. Quick sort
6. Randomized Quick sort (an optimized quick sort)

But, the problem with such sorting algorithms like bubble sort, insertion sort, and the selection sort is they take a lot of time to sort.

For example, If we have to sort an array of 10 elements then any sorting algorithm can be opted but in case of an extensively high value of N that is the no. of elements of the array like if N=1000000 then in case the starting 3 sorting algorithms cannot be opted as the time they will take is proportional to (N*N) which in big O notation can be represented as O(N*N).

So today we will focus on a more optimized sorting algorithm that is (MERGE SORT).

Basically, both merge and quick sort are divide and conquer algorithms.

But today we'll be focusing on MERGE SORT and the main reason of casting light upon this sorting algorithm is it takes O(N*logN) time which is very efficient with respect to the O(N*N).

In merge sort we follow just 3 simple steps to sort an array:

1. Divide the array into two parts
2. Recursively sort both the parts
3. Then, merge those two stored parts into one

Description:

So basically it is considered as one of the best sorting algorithms having a worst case and best case time complexity of O(N*Log(N)), this is the reason that generally we prefer to merge sort over quicksort as quick sort does have a worst-case time complexity of O(N*N).

Let’s quickly jump upto the coding part...

```#include<iostream>
using namespace std;

int temp;

void mergearrays(int ar[],int s,int e)
{
int mid=(s+e)/2;
int i,j;
i=s;  j=mid+1;
int x=s;
while(i<=mid&&j<=e)
{
if(ar[i]<ar[j])
{
temp[x++]=ar[i];
i++;
}

else
{
temp[x++]=ar[j];
j++;
}
}

while(i<=mid)
{
temp[x++]=ar[i];
i++;
}
while(j<=e)
{
temp[x++]=ar[j];
j++;
}

for(int i=s;i<=e;i++)
ar[i]=temp[i];
}

void mergesort(int ar[],int s,int e)
{
int mid=(s+e)/2;
///base case
if(s>=e)
return ;
///recursive case
mergesort(ar,s,mid);
mergesort(ar,mid+1,e);
mergearrays(ar,s,e);
}

int main()
{
int n;

cout<<"Enter total number of elements: ";
cin>>n;

int ar;
cout<<"The unsorted array is (Enter elements): "<<endl;
for(int i=0;i<n;i++)
cin>>ar[i];

mergesort(ar,0,n-1);

cout<<"The sorted array is"<<endl;
for(int i=0;i<n;i++)
cout<<ar[i]<<" ";

return 0;
}
```

Output

```Enter total number of elements: 7
The unsorted array is (Enter elements):
7 4 6 5 3 2 1
The sorted array is
1 2 3 4 5 6 7
```

TOP Interview Coding Problems/Challenges

Learn PCB Designing: PCB DESIGNING TUTORIAL

 Recommended posts C Tips & Tricks, C++ Tips & Tricks Introduction to Linux (Its modes, Safety, Most popular Applications) Linux Best Distros of 2018 C programming optimization techniques Differences b/w C & Embedded C? Embedded C Interview Q. & A. C programming tips for Embedded Development Basic rules of writing a C program Important points (rules) to remember while writing C/C++ program Top 5 Websites for solving programming challenges Read more...

 Others... Computer G.K. (MCQ) Most viewed pages... Categories...

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates