C++ Program For Merge Sort Using Recursion

Merge Sort is a highly efficient, comparison-based sorting algorithm that operates on the divide-and-conquer principle. In this article, you will learn how to implement Merge Sort in C++ using recursion, understand its underlying logic, and see practical examples.

Problem Statement

Efficiently sorting large datasets is a fundamental problem in computer science. Unsorted data makes searching, analysis, and data retrieval slow and cumbersome. The challenge is to arrange elements in a specific order (ascending or descending) with optimal time and space complexity, especially for collections that may not fit entirely into memory.

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 and implement Merge Sort effectively, readers should be familiar with:

• C++ Basics: Variables, data types, arrays, functions, and loops.
• Recursion: Understanding how a function calls itself and the concept of base cases.
• Pointers and Memory Allocation: For dynamic array manipulation (though not strictly necessary for the in-place version, it's good for understanding auxiliary space).
• Algorithm Analysis: Basic understanding of time and space complexity (e.g., Big O notation).

Use Cases or Case Studies

Merge Sort is a versatile algorithm used in various scenarios due to its stability and consistent performance.

• Sorting Large Datasets: Its O(N log N) time complexity makes it suitable for sorting millions or billions of records.
• External Sorting: When data is too large to fit into RAM, Merge Sort can efficiently sort data stored on disk by dividing it into smaller chunks, sorting them, and then merging.
• Linked Lists: Unlike some other algorithms (e.g., Quick Sort), Merge Sort is efficient for sorting linked lists because it doesn't require random access to elements. Merging linked lists is also more efficient than arrays, as it avoids shifting elements.
• Parallel Processing: The divide-and-conquer nature of Merge Sort makes it naturally suitable for parallel implementations, where different sub-problems can be processed simultaneously.
• Stability Requirements: Merge Sort is a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output. This is crucial in applications where original order matters (e.g., sorting a list of students by grade, then by name, without disturbing the original name order for students with the same grade).

Solution Approaches

The primary approach for Merge Sort involves a recursive divide-and-conquer strategy.

Recursive Merge Sort

This approach breaks down the array into smaller halves until each subarray has only one element (which is inherently sorted). It then repeatedly merges these sorted subarrays to produce new sorted subarrays until the entire array is sorted.

The algorithm consists of two main parts:

1. mergeSort(arr, left, right): This recursive function divides the array into two halves.
2. merge(arr, left, mid, right): This function takes two sorted subarrays and merges them into a single sorted array.

Let's walk through the detailed implementation:

Code Example

// Merge Sort using Recursion
#include <iostream>
#include <vector>
#include <algorithm> // For std::min (optional, could use ternary operator)

// Function to merge two sorted subarrays
// arr[left...mid] and arr[mid+1...right]
void merge(std::vector<int>& arr, int left, int mid, int right) {
    // Step 1: Calculate sizes of the two subarrays to be merged
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Step 2: Create temporary arrays for the left and right subarrays
    std::vector<int> L(n1);
    std::vector<int> R(n2);

    // Step 3: Copy data to temporary 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];

    // Step 4: Merge the temporary 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++;
    }

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

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

// Main function that sorts arr[left...right] using merge()
void mergeSort(std::vector<int>& arr, int left, int right) {
    // Step 1: Base case for recursion - if left >= right, the subarray has 0 or 1 element, which is already sorted
    if (left < right) {
        // Step 2: Find the middle point to divide the array into two halves
        int mid = left + (right - left) / 2; // Avoids potential overflow for large left/right

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

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

// 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 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 << "Original array: ";
    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:   ";
    printArray(arr);

    return 0;
}

Run

Sample Output

Original array: 38 27 43 3 9 82 10 
Sorted array:   3 9 10 27 38 43 82

Stepwise Explanation

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

• Base Case: The recursion stops when left >= right. This means the subarray has one or zero elements, which is considered sorted.
• Divide: It calculates the mid point of the current subarray.
• Conquer: It recursively calls mergeSort on the left half (arr[left...mid]) and the right half (arr[mid+1...right]). These recursive calls will sort their respective halves.
• Combine: After the two halves are sorted, it calls the merge function to combine them into a single sorted subarray.

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

• Preparation: It determines the sizes of the two subarrays (n1 for left, n2 for right) and creates two temporary vectors, L and R, to hold their elements.
• Copying Data: The elements from arr[left...mid] are copied into L, and elements from arr[mid+1...right] are copied into R.
• Merging: It uses three pointers: i for L, j for R, and k for the main arr (starting at left).
• It compares 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.
• Remaining Elements: Any remaining elements in L or R (if one array finished before the other) are copied directly into arr. Since these remaining elements are already sorted relative to themselves, they can just be appended.

This recursive process ensures that eventually, all elements are merged in their correct sorted positions.

Conclusion

Merge Sort is a powerful and reliable sorting algorithm, characterized by its O(N log N) time complexity in all cases (best, average, and worst). It provides a stable sort and is particularly well-suited for large datasets and scenarios involving linked lists or external sorting. While it uses additional space for temporary arrays (O(N) space complexity), its consistent performance and stability make it a preferred choice for many applications.

Summary

• Divide and Conquer: Breaks down the problem into smaller, manageable sub-problems (sorting halves), then combines their solutions.
• Recursive: The mergeSort function calls itself to sort subarrays.
• Merging: The merge function is crucial, combining two sorted subarrays into a single sorted array.
• Time Complexity: O(N log N) for best, average, and worst cases, making it very efficient for large inputs.
• Space Complexity: O(N) due to the need for temporary arrays during the merge operation.
• Stability: Preserves the relative order of equal elements.
• Use Cases: Ideal for large datasets, external sorting, linked lists, and situations requiring a stable sort.