Merge Sort Algorithm | Working, Applications & More (+Examples)

11 mins read

Sorting is a fundamental operation in computer science, essential for organizing data efficiently. Among various sorting algorithms, Merge Sort stands out due to its divide-and-conquer approach, ensuring stable and efficient sorting. Developed by John von Neumann in 1945, Merge Sort recursively divides an array into smaller subarrays, sorts them individually, and then merges them back together in a sorted order.

In this article, we will explore the working of Merge Sort, its implementation, time complexity, and why it is preferred over other sorting techniques in certain scenarios.

Understanding The Merge Sort Algorithm

Merge Sort in data structures is based on the Divide and Conquer approach, which breaks a complex problem into smaller subproblems, solves them individually, and then combines the results.

Real-Life Analogy: Organizing a Messy Bookshelf

Imagine you have a huge pile of books scattered randomly, and you want to arrange them in alphabetical order. Instead of sorting the entire pile at once, you can use a systematic approach:

1. Divide: Split the pile into two smaller halves.
2. Conquer: Keep dividing each half further until each section contains just one book (which is already sorted by itself).
3. Combine: Start merging two small piles at a time, ensuring they stay in order, until all books are sorted in a single, neatly arranged bookshelf.

This is exactly how Merge Sort works with an array of numbers!

Explanation Of The Divide-and-Conquer Approach In Merge Sort

1. Divide: The array is recursively divided into two halves until each subarray contains only one element (which is naturally sorted).
2. Conquer: Each pair of small sorted arrays is merged together in sorted order.
3. Combine: The merging continues until we get a fully sorted array.

For example, let’s sort the array [8, 3, 5, 1, 7, 2, 6, 4] using Merge Sort:

1. Divide:

[8, 3, 5, 1]      [7, 2, 6, 4]  
[8, 3]   [5, 1]   [7, 2]   [6, 4]  
[8] [3]  [5] [1]  [7] [2]  [6] [4]

(Each number is now a single-element array.)

2. Conquer (Merge Step):

[3, 8]   [1, 5]   [2, 7]   [4, 6]  
[1, 3, 5, 8]   [2, 4, 6, 7]  
[1, 2, 3, 4, 5, 6, 7, 8]  

Each merge step ensures that the resulting array remains sorted.

Why is Divide and Conquer Efficient?

• Instead of comparing every element with every other element (O(n²) time in Bubble Sort or Insertion Sort), Merge Sort cleverly splits and merges efficiently in O(n log n) time.
• The systematic merging ensures stability, meaning equal elements retain their relative order, which is crucial in certain applications like database sorting.

Thus, Merge Sort leverages Divide and Conquer to sort data efficiently, just like organizing a messy bookshelf in small, manageable steps!

Algorithm For Merge Sort

The main steps in the merge sort algorithm are: 

1. Splitting the Array (Divide Phase)

• We keep recursively dividing the array into two halves until each subarray contains a single element (which is inherently sorted).

2. Sorting and Merging the Subarrays (Conquer & Combine Phase)

• Once we reach the smallest subarrays, we start merging them back in a sorted order.
• This merging process compares elements from two sorted subarrays and arranges them in the correct order.

Pseudocode Representation:

MERGE_SORT(arr, left, right)
1. If left < right:
2.     Find the middle index: mid = (left + right) / 2
3.     Recursively sort the first half: MERGE_SORT(arr, left, mid)
4.     Recursively sort the second half: MERGE_SORT(arr, mid + 1, right)
5.     Merge the sorted halves: MERGE(arr, left, mid, right)

MERGE(arr, left, mid, right)
1. Create two temporary arrays:
       Left subarray = arr[left...mid]
       Right subarray = arr[mid+1...right]
2. Maintain three pointers for Left, Right, and Merged arrays.
3. Compare elements from Left and Right subarrays:
       - Copy the smaller element into the merged array.
       - Move the corresponding pointer forward.
4. If elements remain in either subarray, copy them into the merged array.

Implementation Of Merge Sort In C++

Here’s a C++ program to implement Merge Sort with a step-by-step explanation:

Code Example:

#include <iostream>
using namespace std;

// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // Size of left subarray
    int n2 = right - mid;      // Size of right subarray

    // Create temporary arrays
    int leftArr[n1], rightArr[n2];

    // Copy data into temporary arrays
    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back into arr[left...right]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements of leftArr[], if any
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // Copy remaining elements of rightArr[], if any
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// Merge Sort function (recursively divides and sorts)
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Recursively sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function to test Merge Sort
int main() {
    int arr[] = {8, 3, 5, 1, 7, 2, 6, 4};
    int size = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, size - 1);

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

    return 0;
}

Output:

Original array: 8 3 5 1 7 2 6 4 
Sorted array: 1 2 3 4 5 6 7 8 

Explanation:

In the above code example-

1. We begin by including the <iostream> header file, which allows us to use standard input and output operations.
2. Then we use namespace std; to avoid prefixing std:: before standard library elements.
3. The merge() function is responsible for merging two sorted subarrays into a single sorted subarray.
4. We calculate the sizes of the two subarrays using mid - left + 1 for the left subarray and right - mid for the right subarray.
5. Temporary arrays leftArr and rightArr store elements of the left and right subarrays, respectively.
6. We copy elements from the original array into these temporary arrays.
7. A while loop merges the two temporary arrays back into the original array while maintaining the sorted order.
8. If elements remain in either subarray, we copy them back into the original array.
9. The mergeSort function recursively divides the array into halves until we reach single-element subarrays.
10. Once divided, the function merges the sorted subarrays back using the merge function.
11. The printArray function prints the elements of an array, separating them with spaces.
12. In main() function, we define an integer array {8, 3, 5, 1, 7, 2, 6, 4} and calculate its size.
13. We print the original array using printArray.
14. We call mergeSort, passing the array and its boundaries (0 to size - 1).
15. After sorting, we print the sorted array using printArray.
16. The program follows the divide-and-conquer approach, making recursive calls and merging sorted subarrays efficiently.

Time And Space Complexity Analysis Of Merge Sort

Merge Sort follows the Divide and Conquer approach, recursively breaking down the array and merging sorted subarrays. Below is a detailed analysis of its time and space complexity:

Key Takeaways

• Merge Sort maintains consistent O(n log n) performance across all cases.
• It is not in-place due to its O(n) space requirement, making it less memory-efficient than Quick Sort.
• Suitable for sorting large datasets and linked lists due to its stability and efficiency.

Advantages And Disadvantages Of Merge Sort

Merge Sort is a widely used sorting algorithm known for its efficiency and stability. However, it also has some drawbacks.

Advantages Of Merge Sort

Disadvantages Of Merge Sort Algorithm

Applications Of Merge Sort 

Merge Sort is widely used in real-world applications due to its efficiency and stability. Here are some key areas where it is applied:

1. Sorting Large Datasets – Efficiently sorts massive datasets, especially when dealing with millions of elements.
2. External Sorting (Disk-Based Sorting) – Used when the data does not fit into memory, such as sorting large log files or databases stored on hard drives or SSDs.
3. Linked List Sorting – Performs better than Quick Sort for linked lists since it doesn’t require random access and works efficiently in O(n log n) time.
4. Stable Sorting in Databases – Ensures that records with the same key retain their original order, making it ideal for database management systems (DBMS).
5. Multi-Threaded Sorting – Works well in parallel computing environments since it can divide the problem into smaller parts and sort them concurrently.
6. Genomic and Bioinformatics Applications – Used in DNA sequencing and other computational biology tasks where sorting huge amounts of genetic data is required.
7. Sorting in Graphics and Computer Vision – Helps in image processing tasks, such as sorting pixels by intensity levels for efficient rendering and filtering.

Conclusion

Merge Sort is a powerful and efficient sorting algorithm that follows the Divide and Conquer approach. With its consistent O(n log n) time complexity and stability, it is widely used in applications such as large dataset sorting, linked lists, external sorting, and database management. However, its O(n) space complexity makes it less memory-efficient compared to in-place sorting algorithms like Quick Sort.

Think of Merge Sort like assembling a puzzle—we break it into smaller pieces, sort them individually, and then carefully put them back together to form the final sorted result. While it may not always be the fastest choice for small datasets, its reliability and scalability make it an excellent choice for handling large and complex sorting problems.

Frequently Asked Questions

Q. Why is Merge Sort considered a stable sorting algorithm?

Merge Sort is stable because it maintains the relative order of equal elements in the original array. When merging two sorted subarrays, if two elements have the same value, the element from the left subarray is placed first, preserving their initial order. This property is important in applications like database sorting, where maintaining record order is necessary.

Q. How does Merge Sort use the Divide and Conquer approach?

Merge Sort follows the Divide and Conquer strategy in three steps:

1. Divide – The array is recursively split into two halves until each subarray has only one element.
2. Conquer – Each subarray is sorted independently.
3. Combine (Merge) – The sorted subarrays are merged back in order to produce the final sorted array.

This approach ensures efficient sorting and allows for parallel execution in multi-threaded environments.

Q. Why does Merge Sort always have O(n log n) time complexity?

Merge Sort maintains O(n log n) complexity in all cases because:

• The Divide step always takes log n time, as the array is halved in each recursive call.
• The Merge step takes O(n) time to combine two sorted subarrays.
• Since both steps run for every level of recursion, the overall complexity is O(n log n).

Unlike Quick Sort, which degrades to O(n²) in the worst case, Merge Sort remains consistently efficient.

Q. Why is Merge Sort not an in-place sorting algorithm?

An in-place algorithm sorts data without requiring significant extra memory. Merge Sort algorithm, however, needs O(n) extra space to store temporary subarrays during merging. Because it creates copies of subarrays, it does not modify the original array in place, making it less memory-efficient compared to algorithms like Quick Sort or Heap Sort.

Q. In which scenarios is Merge Sort preferred over Quick Sort?

Merge Sort Algorithm is preferred over Quick Sort Algorithm in the following cases:

• Sorting Linked Lists – Since Merge Sort doesn’t require random access to elements, it performs better on linked lists than Quick Sort.
• Stable Sorting Required – When maintaining the relative order of equal elements is essential, Merge Sort is a better choice.
• Sorting Large Files (External Sorting) – Merge Sort works well for disk-based sorting, where data is too large to fit into memory.
• Worst-Case Performance Matters – Merge Sort guarantees O(n log n) in all cases, whereas Quick Sort can degrade to O(n²) in the worst case.

Suggested Reads:

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions