Merge Sort Algorithm

Merge Sort algorithm is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Merge Sort algorithm is one of the most respected sorting algorithms, with a worst-case time complexity of O(nlogn).

Merge sort works by dividing the array repeatedly to make several single-element arrays.

The concept of merge sort involves breaking down an array of n elements into n individual elements. Why?

As each element can be considered as a sorted array consisting of one element. Then we start to combine these individual single array elements into one final sorted array.

How Does the Merge Sort Algorithm Work?

Divide and Conquer Strategy

Now that we have a fair understanding of what divide and conquer is, let us try and understand how that is done to sort an array of integers.

Let us consider an array, array that consists of n unsorted integers. Our end goal is to sort the array.

Let us consider an array={38,27,43,3,9,82,10}.

1.Divide In this step, we find the midpoint of the given array by using the formula mid=start+(end-start)/2

2. Conquer In this step, we divide the array into subarrays using the midpoint calculated. We recursively keep dividing the array and keep calculating the midpoint for doing the same. It is important to note that a single array element is always sorted.

So, our aim is to continuously divide until all elements in the array are single array elements. Once that is done, the array elements are combined back to form a sorted array.

As mentioned above, our goal is to keep dividing till all elements in the array are single array elements hence, this is the base case i.e. when there are n subarrays of the original array that consisted of n integers. It is now the turn is to sort them and combine them.

3. Combine

Now that all our subarrays are formed, it is now time to combine them in sorted order.

Implementation of Merge Sort Algorithm

Since we start combining when we have subarrays of length 1, when we get 2 subarrays to combine, they will be sorted amongst each other.

It is our job to sort these and put them together in the final sorted array. We accomplish this by having 3 pointers/references.

• At the beginning of the first subarray
• At the beginning of the second subarray
• At the sorted array

Until we reach the end of either of the subarrays, we keep checking which element is smaller and putting that in the array.

Here 1 is smaller, so we push that to the sorted array and then move the pointer of the subarray that contains 1 as the next number after 1 might be smaller or larger than 6 but the number after 6 is definitely larger than 1. We continue as follows:

Now we see that we have reached the end of the second subarray. This means that the remaining numbers in the first sub-array are definitely larger and since they are sorted, we insert them in the final sorted array as-is.

1. Merge Sort Code in Java

2. Merge Sort Code in Python

3. Merge Sort Code in C

4. Merge Sort Code in C++

5. Merge Sort Code in JavaScript

Complexity Analysis of Merge Sort Algorithm

Time Complexity of Merge Sort Algorithm

Merge Sort’s time complexity is O(n*Log n) in worst case, average case, and best case, because it always divides the array into two halves and merges the two halves in linear time.

• Worst Case Time Complexity: O(n*$\log_2(n)$)
• Best Case Time Complexity: O(n*$\log_2(n)$)
• Average Case Time Complexity: O(n*$\log_2(n)$)

Space Complexity of Merge Sort Algorithm

The space complexity of the merge sort algorithm is O(n) where 'n' is the number of elements in the array being sorted.

Applications of Merge sort Algorithm

1. External Merge Sort: Merge sort forms the basis of the external merge sort algorithm, which is commonly used for sorting large datasets that do not fit into main memory. External merge sort divides the data into smaller chunks that can fit into memory, sorts these chunks using merge sort, and then merges the sorted chunks together to produce the final sorted output.

2. Network Routing: Merge sort's divide-and-conquer strategy finds applications in network routing algorithms, where the task involves sorting and merging various routing tables or paths to optimize network traffic flow and minimize congestion.

3. File Processing: Merge sort algorithm can be used for sorting large files containing records or data entries. It efficiently handles the sorting process by dividing the file into manageable chunks, sorting them individually, and then merging them back together to produce the sorted output file.

Advantages of Merge Sort

Merge sort offers several advantages:

1. Stable Sorting: Merge sort is a stable sorting algorithm, it means that it preserves the relative order of equal elements.
2. Predictable Performance: Merge sort has a consistent time complexity of O(n log n) regardless of the input data. This makes it predictable and reliable, especially for large datasets.
3. Efficient for Linked Lists: Merge sort performs well with linked lists due to its ability to efficiently merge two sorted lists into one. This makes it a preferred choice for sorting linked lists over other algorithms like quicksort, which relies heavily on random access to elements.
4. Parallelizable: Merge sort can be easily parallelized, allowing it to take advantage of multiple processors or cores in a system. This property makes it suitable for implementation in parallel computing environments, where performance can be significantly improved.
5. Guaranteed Worst-Case Performance: Unlike quicksort, which can have a worst-case time complexity of O(n^2) for certain input distributions, merge sort always guarantees O(n log n) time complexity, regardless of the input data.

Drawbacks of Merge Sort Algorithm

The drawbacks of Merge Sort are as follows:

• We have seen that we need to store the sorted elements in a separate array of size n, this requires more space thereby increasing the space complexity.
• We have also seen that the pointers traverse through one entire sub-array. Let us consider the case where the subarrays are perfectly sorted.

For example subarray1={1,2,3} and subarray2={4,5,6}. The final sorted array looks like this {1,2,3,4,5,6} which is just subarray2 kept after subarray1 but we still need to traverse the entire array thereby wasting time.

• Merge Sort when considered for smaller arrays can prove to be slower as compared to other algorithms.

Explore Scaler Topics Data Structures Tutorial and enhance your DSA skills with Reading Tracks and Challenges.

Read More

• Merge Sort Program in C++
• Merge Sort in C
• Time Complexity of Merge Sort