C++ Program For Merge Sort With Time Complexity

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. While many algorithms exist, some offer superior performance for large datasets. In this article, you will learn how to implement Merge Sort in C++, understand its underlying mechanism, and analyze its time complexity.

Problem Statement

The challenge is to efficiently sort a collection of elements, such as numbers in an array, into a specific order (ascending or descending). For small arrays, simple algorithms like Bubble Sort or Insertion Sort might suffice. However, as the number of elements grows, these algorithms become prohibitively slow due to their quadratic time complexity, leading to performance bottlenecks in applications. An efficient sorting algorithm is required to handle large datasets effectively.

Example: Merge Sort Conceptual Walkthrough

Let's illustrate how Merge Sort conceptually sorts the array [38, 27, 43, 3, 9, 82, 10].

1. Divide: The array is recursively split into halves until each subarray contains only one element (which is inherently sorted).

• [38, 27, 43, 3, 9, 82, 10]
• [38, 27, 43, 3] and [9, 82, 10]
• [38, 27] and [43, 3] and [9, 82] and [10]
• [38], [27], [43], [3], [9], [82], [10]

1. Conquer (Merge): Sorted subarrays are merged back together to produce new sorted subarrays.

• Merge [38] and [27] → [27, 38]
• Merge [43] and [3] → [3, 43]
• Merge [9] and [82] → [9, 82]
• Merge [10] (already sorted)

1. Continue Merging:

• Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
• Merge [9, 82] and [10] → [9, 10, 82]

1. Final Merge:

• Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

The array is now fully sorted.

Background & Knowledge Prerequisites

To understand and implement Merge Sort in C++, familiarity with the following concepts is beneficial:

• C++ Basics: Fundamental syntax, data types (integers, arrays), and control structures (loops, conditionals).
• Functions: Defining and calling functions, understanding parameters.
• Recursion: The concept of a function calling itself, which is central to Merge Sort's divide-and-conquer strategy.
• Arrays: How to declare, initialize, and access elements in C++ arrays.
• Pointers (Optional but helpful): Understanding how pointers can be used for array manipulation and passing array segments to functions.

Use Cases or Case Studies

Merge Sort's stability and efficient worst-case performance make it suitable for various applications:

• External Sorting: When data is too large to fit into main memory, Merge Sort can process parts of the data from disk, merge them, and write them back. This is crucial in database systems.
• Parallel Sorting: Its divide-and-conquer nature makes it highly suitable for parallelization, where different parts of the array can be sorted concurrently on multiple processors.
• Inversion Count Problem: Merge Sort can be modified to efficiently count the number of inversions in an array, a measure of how "unsorted" an array is.
• Linked List Sorting: Unlike Quick Sort, Merge Sort works very well with linked lists because it doesn't require random access to elements; only sequential access is needed during merging.
• Guaranteed Performance: In scenarios where consistent performance is critical (e.g., real-time systems or applications requiring predictable latency), Merge Sort's O(N log N) worst-case time complexity is a significant advantage over algorithms like Quick Sort, which can degrade to O(N^2).

Solution Approaches: C++ Implementation of Merge Sort

Merge Sort is a classic example of a divide-and-conquer algorithm. It works by dividing an unsorted list into *n* sublists, each containing one element (a list of one element is considered sorted). Then, it repeatedly merges sublists to produce new sorted sublists until there is only one sorted list remaining.

Approach: Recursive Merge Sort

This approach implements Merge Sort using two primary functions: mergeSort for dividing the array and recursively sorting subarrays, and merge for combining two sorted subarrays into one larger sorted array.

One-line summary

Merge Sort recursively divides an array into halves, sorts them, and then merges the sorted halves back together.

Code example

// Merge Sort Implementation
#include <iostream> // For input/output operations
#include <vector>   // For using std::vector

// Function to merge two sorted subarrays
// arr[l..m] and arr[m+1..r] into arr[l..r]
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1; // Size of the left subarray
    int n2 = right - mid;    // Size of the right subarray

    // Create temporary arrays
    std::vector<int> L(n1);
    std::vector<int> 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[mid + 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 of merged subarray

    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 any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

// Main function that implements Merge Sort
// arr is the array to be sorted, left is the starting index, right is the ending index
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) { // Base case: if the array has 0 or 1 element, it's already sorted
        return;
    }
    int mid = left + (right - left) / 2; // Find the middle point to divide the array into two halves
    mergeSort(arr, left, mid);           // Recursively sort the first half
    mergeSort(arr, mid + 1, right);      // Recursively sort the second half
    merge(arr, left, mid, right);        // Merge the sorted halves
}

// Utility function to print an array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Initialize an array
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int arr_size = arr.size();

    // Step 2: Print the original array
    std::cout << "Given array is \\n";
    printArray(arr);

    // Step 3: Call mergeSort to sort the array
    mergeSort(arr, 0, arr_size - 1);

    // Step 4: Print the sorted array
    std::cout << "\\nSorted array is \\n";
    printArray(arr);

    // Test with another array
    std::vector<int> arr2 = {38, 27, 43, 3, 9, 82, 10};
    arr_size = arr2.size();
    std::cout << "\\nGiven array 2 is \\n";
    printArray(arr2);
    mergeSort(arr2, 0, arr_size - 1);
    std::cout << "\\nSorted array 2 is \\n";
    printArray(arr2);

    return 0;
}

Run

Sample output

Given array is 
12 11 13 5 6 7 

Sorted array is 
5 6 7 11 12 13 

Given array 2 is 
38 27 43 3 9 82 10 

Sorted array 2 is 
3 9 10 27 38 43 82

Stepwise explanation for clarity

1. merge(std::vector& arr, int left, int mid, int right) Function:

• This function takes a vector arr and three indices (left, mid, right) representing the bounds of two sorted subarrays to be merged.
• It calculates the sizes of the two subarrays (n1 for arr[left...mid] and n2 for arr[mid+1...right]).
• Two temporary std::vectors, L and R, are created to hold the elements of these subarrays.
• The elements from arr are copied into L and R.
• Pointers i, j, and k are initialized for L, R, and arr respectively.
• It then iteratively compares elements from L[i] and R[j], placing the smaller one into arr[k] and incrementing the respective pointer (i or j) and k.
• After one of the temporary arrays is exhausted, any remaining elements from the other temporary array are copied directly into arr. This ensures all elements are moved back into the original array in sorted order.

1. mergeSort(std::vector& arr, int left, int right) Function:

• This is the recursive main function for Merge Sort.
• Base Case: If left >= right, it means the subarray has 0 or 1 element, which is already sorted. The function returns without further action.
• Divide: It calculates the mid point of the current subarray.
• Conquer:
• It recursively calls mergeSort for the left half (arr[left...mid]).
• It recursively calls mergeSort for the right half (arr[mid+1...right]).
• Combine: After both halves are sorted, it calls the merge function to combine the two sorted halves into a single sorted subarray.

1. main() Function:

• An std::vector arr is initialized with unsorted integers.
• The printArray function displays the original content.
• mergeSort is called with the array, starting index (0), and ending index (arr.size() - 1).
• After sorting, printArray shows the sorted array.
• A second test case is included to demonstrate the algorithm's robustness.

Time Complexity Analysis

Merge Sort exhibits consistent performance regardless of the initial state of the input array.

• Divide Step: Dividing the array into two halves takes constant time, O(1).
• Conquer (Recursive Calls): This step involves two recursive calls to mergeSort on halves of the array. If T(N) is the time taken to sort N elements, then this part contributes 2T(N/2).
• Combine (Merge Step): The merge function takes two sorted subarrays and merges them. In the worst case, it iterates through all N elements once. Thus, merging takes O(N) time.

Combining these, the recurrence relation for Merge Sort's time complexity is: T(N) = 2T(N/2) + O(N)

Solving this recurrence relation using the Master Theorem or by drawing a recursion tree reveals that Merge Sort's time complexity is O(N log N) in all cases (best, average, and worst).

• Space Complexity: Merge Sort requires O(N) auxiliary space for the temporary arrays used during the merge operation.

Conclusion

Merge Sort is a highly efficient, comparison-based sorting algorithm known for its consistent performance. Its divide-and-conquer approach ensures an O(N log N) time complexity in all scenarios, making it a reliable choice for sorting large datasets. While it uses additional space for temporary arrays, its stability and suitability for parallel processing and external sorting often outweigh this drawback.

Summary

• Merge Sort is a divide-and-conquer sorting algorithm.
• It recursively divides the array into halves until individual elements are reached.
• Sorted subarrays are then merged to create larger sorted arrays.
• Time Complexity: O(N log N) for best, average, and worst cases.
• Space Complexity: O(N) auxiliary space due to temporary arrays used in merging.
• It is a stable sorting algorithm (maintains the relative order of equal elements).
• Well-suited for large datasets, external sorting, and linked lists.