C++ Program For Merge Sort Taking Input From User

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. In this article, you will learn how to implement the Merge Sort algorithm in C++, allowing users to input an array of numbers to be sorted.

Problem Statement

Efficiently arranging a collection of elements into a specific order, such as ascending or descending, is a common requirement in many applications. When dealing with user-provided data, the sorting mechanism must be robust, handle varying input sizes, and perform well. The challenge is to sort an array of integers provided by the user without sacrificing performance, making algorithms like Merge Sort particularly relevant due to their guaranteed O(n log n) time complexity.

Example

Consider an unsorted list of numbers: [38, 27, 43, 3, 9, 82, 10]. After applying Merge Sort, the sorted list will be: [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, loops (for, while), and conditional statements (if/else).
• Functions: Defining and calling functions, passing arguments by value and by reference.
• Input/Output Operations: Using std::cin for user input and std::cout for displaying output.
• Recursion: The concept of a function calling itself.
• std::vector: Basic usage of dynamic arrays in C++.

Use Cases or Case Studies

Merge Sort is highly versatile and finds application in various scenarios:

• External Sorting: When data to be sorted is too large to fit into memory, Merge Sort is ideal as it can efficiently sort data stored on disk.
• Parallel Sorting: Its divide-and-conquer nature makes it suitable for parallel processing, where different sub-arrays can be sorted concurrently.
• Linked Lists: Merge Sort performs exceptionally well on linked lists because it doesn't require random access to elements, unlike algorithms like Quick Sort.
• Inversion Count Problem: It can be adapted to count inversions in an array, a measure of how far an array is from being sorted.
• Genetic Algorithms: Often used as a subroutine for sorting populations based on fitness values.

Solution Approaches

Approach: Recursive Merge Sort Implementation with User Input

This approach details the classic recursive Merge Sort algorithm, breaking down the array into smaller sub-arrays, sorting them, and then merging them back together. The main function will handle user input for array size and elements.

// Merge Sort with User Input
#include <iostream> // For input/output operations
#include <vector>   // For dynamic array (vector)

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

    // Create temporary arrays
    std::vector<int> L(n1);
    std::vector<int> 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];

    // Merge the temporary arrays back into arr[left...right]
    int i = 0; // Initial index of first sub-array
    int j = 0; // Initial index of second sub-array
    int k = left; // Initial index of merged sub-array

    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++;
    }
}

// Function to perform Merge Sort
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) { // Base case: array with 0 or 1 element is already sorted
        return;
    }
    int mid = left + (right - left) / 2; // Calculate midpoint to avoid overflow
    mergeSort(arr, left, mid);           // Sort first half
    mergeSort(arr, mid + 1, right);      // Sort second half
    merge(arr, left, mid, right);        // Merge the sorted halves
}

int main() {
    // Step 1: Get array size from user
    int size;
    std::cout << "Enter the number of elements: ";
    std::cin >> size;

    if (size <= 0) {
        std::cout << "Number of elements must be positive." << std::endl;
        return 1; // Indicate an error
    }

    // Step 2: Get array elements from user
    std::vector<int> arr(size);
    std::cout << "Enter " << size << " integers:" << std::endl;
    for (int i = 0; i < size; ++i) {
        std::cout << "Element " << i + 1 << ": ";
        std::cin >> arr[i];
    }

    // Step 3: Display the original array
    std::cout << "\\nOriginal array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 4: Perform Merge Sort
    mergeSort(arr, 0, size - 1);

    // Step 5: Display the sorted array
    std::cout << "Sorted array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample Output:

Enter the number of elements: 7
Enter 7 integers:
Element 1: 38
Element 2: 27
Element 3: 43
Element 4: 3
Element 5: 9
Element 6: 82
Element 7: 10

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

Stepwise Explanation:

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

• This function is responsible for merging two sorted sub-arrays back into a single sorted array.
• It takes the main array arr, and the left, mid, and right indices defining the boundaries of the two sub-arrays to be merged (arr[left...mid] and arr[mid+1...right]).
• Temporary arrays L and R are created to hold the elements of the two sub-arrays.
• Elements from L and R are compared, and the smaller element is placed into the correct position in the original array arr, incrementing the respective pointers (i, j, k).
• Any remaining elements in L or R are copied directly to arr.

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

• This is the main recursive function for Merge Sort.
• Base Case: If left >= right, it means the sub-array has zero or one element, which is already sorted, so the recursion stops.
• Divide: The mid index is calculated to divide the array into two halves. This calculation left + (right - left) / 2 is used to prevent potential integer overflow that (left + right) / 2 might cause with very large left and right values.
• Conquer: mergeSort is called recursively for the left half (arr[left...mid]) and the right half (arr[mid+1...right]). This continues until the base case is reached.
• Combine: After the sub-arrays are sorted, the merge function is called to combine the two sorted halves back into a single sorted array.

1. main() Function:

• User Input for Size: The program prompts the user to enter the number of elements they wish to sort. Basic validation ensures the size is positive.
• User Input for Elements: A std::vector named arr is declared with the specified size. The program then iteratively prompts the user to enter each integer element, storing it in the vector.
• Display Original Array: The content of the arr vector is displayed before sorting to show its initial state.
• Call mergeSort: The mergeSort function is called with the arr vector, starting from index 0 to size - 1.
• Display Sorted Array: After the mergeSort function completes, the content of the arr vector is displayed again, now showing the elements in sorted order.

Conclusion

Merge Sort is a powerful, efficient, and stable sorting algorithm with a consistent O(n log n) time complexity. Its divide-and-conquer strategy makes it suitable for various applications, especially when dealing with large datasets or linked lists. Implementing it in C++ allows for robust handling of user-provided data, offering a reliable solution for ordering elements.

Summary

• Merge Sort is a recursive, divide-and-conquer sorting algorithm.
• It works by dividing an array into two halves, recursively sorting each half, and then merging the sorted halves.
• The merge function is crucial; it combines two sorted sub-arrays into a single sorted array efficiently.
• Time Complexity: Offers a consistent O(n log n) in all cases (best, average, worst).
• Space Complexity: Requires O(n) auxiliary space due to the temporary arrays used in the merge step.
• User Input: C++ std::vector and std::cin facilitate taking dynamic array input from the user.