Home » Algorithms

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[10000];

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[10000];
	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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







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

© https://www.includehelp.com some rights reserved.