# 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,

- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quick sort
- 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:

- Divide the array into two parts
- Recursively sort both the parts
- 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.