Introduction

Merge Sort is a divide-and-conquer algorithm that sorts an array by dividing it into two halves, recursively sorting the halves, and then merging them back together. This algorithm has a time complexity of O(n log n) and is very efficient for large datasets.

Program Structure

The implementation consists of the following main components:

• Merge Function: This function takes two sorted halves of an array and merges them into a single sorted array.
• Merge Sort Function: This function recursively divides the array into halves and calls the merge function to sort and combine them.
• Main Function: This is where the program execution begins. It initializes the array, calls the merge sort function, and prints the sorted array.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

// Function to merge two halves
void merge(vector& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector L(n1), R(n2);

    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, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Recursive function to perform merge sort
void mergeSort(vector& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// Main function
int main() {
    vector arr = {12, 11, 13, 5, 6, 7};
    int arr_size = arr.size();

    cout << "Given array is: ";
    for (int i : arr)
        cout << i << " ";
    cout << endl;

    mergeSort(arr, 0, arr_size - 1);

    cout << "Sorted array is: ";
    for (int i : arr)
        cout << i << " ";
    cout << endl;

    return 0;
}

Explanation of Code

– Merge Function: This function merges two sorted subarrays into a single sorted subarray. It creates two temporary arrays to hold the values of the left and right halves. It then compares the elements of these arrays and merges them back into the original array in sorted order.

– Merge Sort Function: This function checks if the array can be divided further (i.e., left is less than right). It calculates the mid-point of the array, recursively calls itself to sort both halves, and then merges them using the merge function.

– Main Function: The main function initializes the array to be sorted, calls the merge sort function, and then prints the sorted array.

Conclusion

Merge Sort is a stable and efficient sorting algorithm that is widely used due to its performance on large datasets. The implementation provided above illustrates the key components and structure of the algorithm in C++.