An Introduction to the Merge Sort Algorithm

Yuvraj is a passionate technical writer with a computer science degree from the esteemed University of Delhi, India.

His deep understanding and expertise in programming, software development, artificial intelligence, and blockchain have driven his passion for writing on cutting-edge technology. Since 2019, he has been a technical writer, sharing his knowledge on various web development technologies. Yuvraj's stint as a developer for several startups complements his writing skills.

In addition to his professional pursuits, Yuvraj enjoys playing chess and has contributed to prominent publications, including GeeksforGeeks. 

Merge sort is a sorting algorithm based on the "divide and conquer" technique. It's one of the most efficient sorting algorithms.

In this article, you'll learn about the working of the merge sort algorithm, the algorithm of the merge sort, its time and space complexity, and its implementation in various programming languages like C++, Python, and JavaScript.

Merge sort works on the principle of divide and conquer. Merge sort repeatedly breaks down an array into two equal subarrays until each subarray consists of a single element. Finally, all those subarrays are merged such that the resultant array is sorted.

This concept can be explained more efficiently with the help of an example. Consider an unsorted array with the following elements: {16, 12, 15, 13, 19, 17, 11, 18}.

Here, the merge sort algorithm divides the array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Below is the algorithm of the merge sort:

MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)

Related: What Is Recursion and How Do You Use It?

The Merge sort algorithm can be expressed in the form of the following recurrence relation:

T(n) = 2T(n/2) + O(n)

After solving this recurrence relation using the master's theorem or recurrence tree method, you'll get the solution as O(n logn). Thus, the time complexity of the merge sort algorithm is O(n logn).

The best-case time complexity of the merge sort: O(n logn)

The average-case time complexity of the merge sort: O(n logn)

The worst-case time complexity of the merge sort: O(n logn)

Related: What Is Big-O Notation?

The auxiliary space complexity of the merge sort algorithm is O(n) as n auxiliary space is required in the merge sort implementation.

Below is the C++ implementation of the merge sort algorithm:

// C++ implementation of the
// merge sort algorithm
#include
using namespace std;

// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;

// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];

// Copying data to temporary arrays L[] and R[]
for (int i = 0; i = rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}


// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i 

Output:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Below is the JavaScript implementation of the merge sort algorithm:

// JavaScript implementation of the
// merge sort algorithm

// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;

// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);

// Copying data to temporary arrays L[] and R[]
for(let i = 0; i= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}

// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i

Output:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Related: Dynamic Programming: Examples, Common Problems, and Solutions

Below is the Python implementation of the merge sort algorithm:

# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:

# Finding the middle index of the array
middleIndex = len(arr)http://2

# Left half of the array
L = arr[:middleIndex]

# Right half of the array
R = arr[middleIndex:]

# Sorting the first half of the array
mergeSort(L)

# Sorting the second half of the array
mergeSort(R)

# Initial index of Left subarray
i = 0

# Initial index of Right subarray
j = 0

# Initial index of merged subarray
k = 0

# Copy data to temp arrays L[] and R[]
while i 

Output:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

Sorting is one of the most used algorithms in programming. You can sort elements in different programming languages using various sorting algorithms like quick sort, bubble sort, merge sort, insertion sort, etc.

Bubble sort is the best choice if you want to learn about the simplest sorting algorithm.