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}.
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:
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)
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:
Output:
JavaScript Implementation of the Merge Sort Algorithm
Below is the JavaScript implementation of the merge sort algorithm:
Output:
Python Implementation of the Merge Sort Algorithm
Below is the Python implementation of the merge sort algorithm:
Output:
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.
