# Merge Sort Algorithm: What It is, Time Complexity, and C++ Implementation

Merge Sort Algorithm: In this tutorial, we will learn about merge sort, its algorithm, and its implementation using C++ program. By Ankit Sood Last updated : August 12, 2023

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

## Problem with other sorting techniques Vs. Why to use merge 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**.

## Merge Sort Algorithm

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)**.

Merge Sort Algorithm 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)**.

## Basic steps

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

## Merge sort algorithm Implementation using C++

The below is the implementation of merge sort using C++ program:

#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; }

The output of the above program will be:

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

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!