C++ Program For Merge Sort Using Divide And Conquer

In this article, you will learn how to implement Merge Sort in C++ using the divide and conquer paradigm, understand its mechanics, and see practical examples.

Problem Statement

Efficiently sorting large datasets is a fundamental challenge in computer science. Simple sorting algorithms like Bubble Sort or Selection Sort become prohibitively slow for large inputs due to their quadratic time complexity (O(n²)). For applications requiring faster performance, especially with increasing data volumes, a more sophisticated approach is necessary to reduce the processing time.

Example

Consider an unsorted array of integers: {38, 27, 43, 3, 9, 82, 10}. After applying Merge Sort, the array will be sorted in ascending order: {3, 9, 10, 27, 38, 43, 82}.

Background & Knowledge Prerequisites

To understand Merge Sort, it's beneficial to have a grasp of:

• C++ Basics: Fundamental syntax, variables, data types, and functions.
• Arrays: How to declare, initialize, and manipulate arrays.
• Recursion: Understanding how functions can call themselves and the concept of a base case.
• Pointers (optional but helpful): For dynamically allocated arrays or passing arrays to functions.

Use Cases or Case Studies

Merge Sort is a versatile algorithm used in various scenarios:

• External Sorting: When data to be sorted is too large to fit into RAM, Merge Sort can efficiently sort chunks of data from disk and then merge them.
• Stable Sorting: If maintaining the relative order of equal elements is important, Merge Sort is a stable sorting algorithm. This is crucial in database systems or when sorting objects with multiple keys.
• Parallel Processing: The divide and conquer nature of Merge Sort makes it highly suitable for parallelization, where different sub-arrays 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, which is a measure of how far an array is from being sorted.
• Linked Lists: Unlike quicksort, Merge Sort can efficiently sort linked lists in O(n log n) time without requiring extra space for random access, as it only needs sequential access.

Solution Approaches

Merge Sort is a classic example of the divide and conquer strategy. It works by breaking down a list into several sub-lists until each sub-list consists of a single element (which is by definition sorted). Then, these sub-lists are repeatedly merged to produce new sorted sub-lists until there is only one sorted list remaining.

Here's the detailed approach:

1. Divide Step: mergeSort Function

Summary: Recursively divides the array into two halves until individual elements are reached.

Code Example:

// Merge Sort using Divide and Conquer
#include <iostream>
#include <vector> // Using vector for dynamic array behavior
#include <algorithm> // For std::copy

// Function to merge two sorted subarrays
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary vectors for left and right halves
    std::vector<int> L(n1);
    std::vector<int> R(n2);

    // Copy data to temporary vectors 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 temporary vectors 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
void mergeSort(std::vector<int>& arr, int left, int right) {
    // Base case: if the subarray has 0 or 1 element, it's already sorted
    if (left >= right) {
        return;
    }
    
    // Find the middle point to divide the array into two halves
    int mid = left + (right - left) / 2;

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

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

// Utility function to print the 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 unsorted array
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    int arr_size = arr.size();

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

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

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

    return 0;
}

Run

Sample Output:

Given array is: 38 27 43 3 9 82 10 
Sorted array is: 3 9 10 27 38 43 82

Stepwise Explanation for Clarity:

1. mergeSort(arr, left, right) Function:

• Base Case: If left is greater than or equal to right, it means the subarray has 0 or 1 element, which is considered sorted. The recursion stops here.
• Find Midpoint: Calculates the middle index mid to divide the current subarray into two halves. Using left + (right - left) / 2 prevents potential integer overflow compared to (left + right) / 2 for very large left and right.
• Recursive Calls:
• mergeSort(arr, left, mid): Recursively calls mergeSort to sort the left half of the subarray.
• mergeSort(arr, mid + 1, right): Recursively calls mergeSort to sort the right half of the subarray.
• Merge: After the left and right halves are sorted (due to the recursive calls reaching the base case and returning), merge(arr, left, mid, right) is called to combine these two sorted halves into a single sorted subarray.

1. merge(arr, left, mid, right) Function:

• Calculate Sizes: Determines the sizes (n1, n2) of the two subarrays to be merged.
• Create Temporary Arrays: Two temporary std::vectors, L and R, are created to hold the elements of the left and right subarrays, respectively.
• Copy Data: Elements from arr[left...mid] are copied into L, and elements from arr[mid+1...right] are copied into R.
• Merge Back:
• Three pointers i, j, and k are initialized. i for L, j for R, and k for the main arr starting from left.
• It compares elements from L[i] and R[j]. The smaller element is placed into arr[k], and its respective pointer (i or j) and k are incremented.
• This continues until one of the temporary arrays is exhausted.
• Copy Remaining Elements: If there are any remaining elements in L or R (meaning the other array was exhausted first), they are copied directly to arr, as they are already sorted.

1. main() Function:

• An initial unsorted std::vector is declared.
• The mergeSort function is called with the array, its starting index (0), and its ending index (arr_size - 1).
• The sorted array is then printed to the console.

Conclusion

Merge Sort is an efficient, comparison-based sorting algorithm with a time complexity of O(n log n) in all cases (best, average, and worst). Its divide and conquer approach, combined with its stability and suitability for external sorting and parallel processing, makes it a valuable tool in various computing applications. While it uses additional space for temporary arrays (O(n) space complexity), its predictable performance and robustness are significant advantages.

Summary

• Merge Sort uses a divide and conquer strategy.
• It recursively divides the array into halves until individual elements are reached.
• Then, it merges sorted subarrays back together.
• It has a time complexity of O(n log n), making it efficient for large datasets.
• It is a stable sorting algorithm.
• Requires O(n) auxiliary space for temporary arrays during the merge operation.
• Well-suited for external sorting and parallelization.