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.

How Does the Merge Sort Algorithm Work?

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}.

Merge sort algorithm example

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

Merge Sort Algorithm

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?

Time and Space Complexity of the Merge Sort Algorithm

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.

C++ Implementation of the Merge Sort Algorithm

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

        // C++ implementation of the
// merge sort algorithm
#include <iostream>
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 < leftSubarraySize; i++)
 L[i] = arr[leftIndex + i];
 for (int j = 0; j < rightSubarraySize; j++)
 R[j] = arr[middleIndex + 1 + j];

// Merge the temporary arrays back into arr[leftIndex..rightIndex]

// Initial index of Left subarray
 int i = 0;

// Initial index of Right subarray
 int j = 0;

// Initial index of merged subarray
 int k = leftIndex;

while (i < leftSubarraySize && j < rightSubarraySize)
 {
 if (L[i] <= R[j])
 {
 arr[k] = L[i];
 i++;
 }
 else
 {
 arr[k] = R[j];
 j++;
 }
 k++;
 }

// If there're some remaining elements in L[]
// Copy to arr[]
 while (i < leftSubarraySize)
 {
 arr[k] = L[i];
 i++;
 k++;
 }

// If there're some remaining elements in R[]
// Copy to arr[]
 while (j < rightSubarraySize)
 {
 arr[k] = R[j];
 j++;
 k++;
 }
}

void mergeSort(int arr[], int leftIndex, int rightIndex)
{
 if(leftIndex >= 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 < size; i++)
 {
 cout << arr[i] << " ";
 }
 cout << endl;
}

// Driver code
int main()
{
 int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
 int size = sizeof(arr) / sizeof(arr[0]);

cout << "Unsorted array:" << endl;
 printArray(arr, size);

mergeSort(arr, 0, size - 1);

cout << "Sorted array:" << endl;
 printArray(arr, size);

return 0;
}

Output:

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

JavaScript Implementation of the Merge Sort Algorithm

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<leftSubarraySize; i++) {
 L[i] = arr[leftIndex + i];
 }
 for (let j = 0; j<rightSubarraySize; j++) {
 R[j] = arr[middleIndex + 1 + j];
 }

// Merge the temporary arrays back into arr[leftIndex..rightIndex]

// Initial index of Left subarray
 var i = 0;

// Initial index of Right subarray
 var j = 0;

// Initial index of merged subarray
 var k = leftIndex;

while (i < leftSubarraySize && j < rightSubarraySize)
 {
 if (L[i] <= R[j])
 {
 arr[k] = L[i];
 i++;
 }
 else
 {
 arr[k] = R[j];
 j++;
 }
 k++;
 }

// If there're some remaining elements in L[]
// Copy to arr[]
 while (i < leftSubarraySize)
 {
 arr[k] = L[i];
 i++;
 k++;
 }

// If there're some remaining elements in R[]
// Copy to arr[]
 while (j < rightSubarraySize)
 {
 arr[k] = R[j];
 j++;
 k++;
 }
}

function mergeSort(arr, leftIndex, rightIndex) {
 if(leftIndex >= 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<size; i++) {
 document.write(arr[i] + " ");
 }
 document.write("
");
}

// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;

document.write("Unsorted array:
");
printArray(arr, size);

mergeSort(arr, 0, size - 1);

document.write("Sorted array:
");
printArray(arr, size);

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

Python Implementation of the Merge Sort Algorithm

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)//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 < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i = i + 1
            else:
                arr[k] = R[j]
                j = j + 1
            k = k + 1

        # Checking if there're some remaining elements
        while i < len(L):
            arr[k] = L[i]
            i = i + 1
            k = k + 1

        while j < len(R):
            arr[k] = R[j]
            j = j + 1
            k = k + 1

# Function to print the elements
# of the array
def printArray(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()


# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)

print("Unsorted array:")
printArray(arr, size)

mergeSort(arr)

print("Sorted array:")
printArray(arr, size)

Output:

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

Understand Other Sorting Algorithms

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.