Installation and Configuration
Programming Methodology

MergeSort Algorithm in C++

In this exercise, you will implement the MergeSort algorithm in C++. MergeSort is a highly efficient, divide-and-conquer sorting algorithm that works by dividing the input array into two halves, sorting each half recursively, and then merging the two sorted halves back together. It has a time complexity of O(n log n), making it an excellent choice for sorting large datasets. The algorithm is stable, meaning that it preserves the relative order of records with equal keys. Implementing MergeSort will help you understand the concept of recursion and the importance of efficient sorting algorithms.

Group

Search and Sort Algorithms in C++

Objective

Write a C++ program that implements the MergeSort algorithm. The program should sort an array of integers in ascending order using the divide-and-conquer technique. Implement the merge function to combine two sorted arrays into one sorted array.

Implement the MergeSort algorithm.

Example C++ Exercise

 Copy C++ Code 
#include <iostream>  // Include the input-output stream library
#include <vector>     // Include the vector library to use dynamic arrays
using namespace std;

// Function to merge two sorted subarrays into a single sorted array
void merge(vector<int> &arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // Size of the first subarray
    int n2 = right - mid;     // Size of the second subarray

    // Create temporary arrays to hold the data
    vector<int> L(n1), R(n2);

    // 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];
    }

    int i = 0;  // Initial index of the first subarray
    int j = 0;  // Initial index of the second subarray
    int k = left;  // Initial index of the merged subarray

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

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

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

// Function to implement MergeSort recursively
void mergeSort(vector<int> &arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // Find the midpoint

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

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

int main() {
    // Define an array to be sorted
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};

    // Get the number of elements in the array
    int size = arr.size();

    // Call mergeSort to sort the array
    mergeSort(arr, 0, size - 1);

    // Display the sorted array
    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

 Output

Sorted array: 3 9 10 27 38 43 82

Share this C++ Exercise


More C++ Programming Exercises of Search and Sort Algorithms in C++

Explore our set of C++ Programming Exercises! Specifically designed for beginners, these exercises will help you develop a solid understanding of the basics of C++. From variables and data types to control structures and simple functions, each exercise is crafted to challenge you incrementally as you build confidence in coding in C++.