Merge Sort in C++

Algorithm

The merge sort algorithm follows these steps:

• Divide the unsorted array into two halves by finding the middle point.
   
• Recursively sort the two halves by calling the merge sort function on each half.
   
• Merge the two sorted halves back together to produce the final sorted array.
   

The merging process works as follows:

• Create two temporary arrays, L & R, to store the elements of the two halves.
   
• Compare the elements of L & R one by one & place the smaller element into the original array.
   
• If there are remaining elements in either L or R, append them to the end of the original array.
   

Here's a visual representation of the merge sort algorithm:

[8, 3, 5, 1, 9, 4, 2, 7]
                        /         \
           [8, 3, 5, 1]           [9, 4, 2, 7]
              /     \                 /     \
        [8, 3]     [5, 1]         [9, 4]   [2, 7]
        /   \       /   \         /   \     /   \
      [8]   [3]   [5]   [1]     [9]   [4] [2]   [7]
        \   /       \   /         \   /     \   /
        [3, 8]     [1, 5]         [4, 9]   [2, 7]
              \     /                 \     /
           [1, 3, 5, 8]           [2, 4, 7, 9]
                        \         /
                 [1, 2, 3, 4, 5, 7, 8, 9]

The algorithm recursively divides the array into smaller subarrays until each subarray contains only one element. Then, it merges the sorted subarrays back together to obtain the final sorted array.

How Merge Sort Works?

Let's walk through an example to understand how merge sort works. Consider the following unsorted array:

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

Divide the array into two halves:

[8, 3, 5, 1] | [9, 4, 2, 7]

Recursively divide the left half:

[8, 3] | [5, 1]

Recursively divide the left subarray:

[8] | [3]

Merge the sorted left subarray:

[3, 8]

Recursively divide the right subarray:

[5] | [1]

Merge the sorted right subarray:

[1, 5]

Merge the sorted left & right subarrays:

[1, 3, 5, 8]

Recursively divide the right half:

[9, 4] | [2, 7]

Recursively divide the left subarray:

[9] | [4]

Merge the sorted left subarray:

[4, 9]

Recursively divide the right subarray:

[2] | [7]

Merge the sorted right subarray:

[2, 7]

Merge the sorted left & right subarrays:

[2, 4, 7, 9]

Merge the sorted left & right halves:

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

The final result is the sorted array.

Implementation in C++

• C++

C++

#include <iostream>
using namespace std;

// Function to merge two halves into a sorted array
void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1; // Number of elements in the first half
    int n2 = right - middle; // Number of elements in the second half

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[middle + 1 + j];

    // Merge the temp arrays back into arr[left..right]
    int i = 0; // Initial index of first subarray
    int j = 0; // Initial index of second subarray
    int k = left; // Initial index to be sorted

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

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

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

// Function to sort the elements using merge sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Same as (left + right)/2, but avoids overflow for large left and right
        int middle = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

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

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

// Main function to run the program
int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Given array is \n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Given array is 
12 11 13 5 6 7
Sorted array is 
5 6 7 11 12 13 

Explanation

1. merge function: This function takes care of merging two sorted halves. It uses temporary arrays to hold values, compares them & then combines them back into the main array.
    
2. mergeSort function: This is the recursive function that continuously splits the array & calls itself until the base condition (subarray with a single element) is reached. It then begins the merging process.
    
3. printArray function: Simply prints out the array elements, helpful for seeing the array before & after sorting.

Time & Space Complexity

Understanding the time & space complexity of merge sort is crucial for appreciating its efficiency in different scenarios. Here’s a straightforward explanation:

Time Complexity

Best, Average, & Worst Cases

Merge sort has a time complexity of O(nlogn) in all three cases: best, average, & worst. This is because the algorithm consistently divides the array in half & then merges it, which requires logn divisions & n comparisons & merges at each level.

Why O(nlogn)?:

Each level of recursion involves a total of n operations (merging two halves), & since the array is divided logn times, the total operations amount to n×logn. This logarithmic division followed by linear merging gives merge sort its O(nlogn) complexity.

Space Complexity

Auxiliary Space

• Merge sort requires additional space for the temporary arrays used during the merging process. This space is proportional to the size of the array being sorted.
   
• The space complexity of merge sort is O(n) because, in the worst case, it needs to store 
   
• n elements temporarily during the merge process.

Practical Implications

• Time Complexity: The O(nlogn) time complexity makes merge sort a highly efficient sorting method, especially for large datasets where less efficient algorithms (like bubble sort or insertion sort) may take prohibitively long.
   
• Space Complexity: Although merge sort is efficient in terms of time, its need for additional space can be a drawback, especially in environments where memory is limited.

Frequently Asked Questions

Why is merge sort preferred over other sorting algorithms like quicksort in certain scenarios?

Merge sort is preferred for its consistent performance (O(nlogn)) regardless of the input data arrangement, unlike quicksort, which can degrade to O(n ²) in worst-case scenarios. It’s also stable, meaning it maintains the relative order of equal elements, which is crucial for certain applications.

Can merge sort be used for linked lists as well as arrays?

Yes, merge sort is highly effective for linked lists. It doesn’t require additional space for array indexes, and nodes can be moved around without additional memory, making it space-efficient for linked lists.

How does merge sort handle large data sets?

Merge sort is excellent for sorting large datasets because it divides the data into manageable chunks, which reduces the overhead seen with algorithms that require significant comparisons or swaps in memory.

Conclusion

In this article, we have learned the detailed process of merge sort in C++. Starting from the fundamental concept of how this algorithm divides and conquers the sorting problem, we walked through the pseudocode, discussed its actual implementation in C++, and analyzed both its time and space complexities.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.