Merge Sort

#include <iostream>
using namespace std;

// Function to merge two sorted halves of an array
void merge(int *arr, int s, int e) {
    int mid = (s + e) / 2; // Find the middle index

    int len1 = mid - s + 1; // Length of left subarray
    int len2 = e - mid;     // Length of right subarray

    // Create temporary arrays
    int *first = new int[len1];
    int *second = new int[len2];

    // Copy elements into the left subarray
    int mainArrayIndex = s;
    for (int i = 0; i < len1; i++) {
        first[i] = arr[mainArrayIndex++];
    }

    // Copy elements into the right subarray
    mainArrayIndex = mid + 1;
    for (int i = 0; i < len2; i++) {
        second[i] = arr[mainArrayIndex++];
    }

    // Merge the two sorted subarrays
    int index1 = 0, index2 = 0;
    mainArrayIndex = s; // Start merging at the original index

    while (index1 < len1 && index2 < len2) {
        if (first[index1] < second[index2]) {
            arr[mainArrayIndex++] = first[index1++];
        } else {
            arr[mainArrayIndex++] = second[index2++];
        }
    }

    // Copy any remaining elements from the left subarray
    while (index1 < len1) {
        arr[mainArrayIndex++] = first[index1++];
    }

    // Copy any remaining elements from the right subarray
    while (index2 < len2) {
        arr[mainArrayIndex++] = second[index2++];
    }

    // Free up dynamically allocated memory
    delete[] first;
    delete[] second;
}

// Function to perform Merge Sort
void mergeSort(int *arr, int s, int e) {
    // Base case: If the array has one or no elements, return
    if (s >= e) {
        return;
    }

    int mid = (s + e) / 2; // Find the middle index

    // Recursively sort the left half
    mergeSort(arr, s, mid);

    // Recursively sort the right half
    mergeSort(arr, mid + 1, e);

    // Merge the sorted halves
    merge(arr, s, e);
}

int main() {
    int arr[15] = {3, 7, 0, 1, 5, 8, 3, 2, 34, 66, 87, 23, 12, 12, 12}; // Sample array
    int n = 15; // Size of the array

    // Perform merge sort on the array
    mergeSort(arr, 0, n - 1);

    // Print the sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Example Walkthrough:

Input Array

[3, 7, 0, 1, 5, 8, 3, 2, 34, 66, 87, 23, 12, 12, 12]

• Recursive Splitting

Left: [3, 7, 0, 1, 5, 8, 3, 2]     Right: [34, 66, 87, 23, 12, 12, 12]
Further split:
[3, 7, 0, 1]  [5, 8, 3, 2]  [34, 66, 87]  [23, 12, 12, 12]

• Sorting and Merging

Merge [3, 7, 0, 1] → [0, 1, 3, 7]
Merge [5, 8, 3, 2] → [2, 3, 5, 8]
Merge [0, 1, 3, 7] and [2, 3, 5, 8] → [0, 1, 2, 3, 3, 5, 7, 8]

• Final Merge

Merge [0, 1, 2, 3, 3, 5, 7, 8] and [12, 12, 12, 23, 34, 66, 87]
Sorted Array: [0, 1, 2, 3, 3, 5, 7, 8, 12, 12, 12, 23, 34, 66, 87]

• Final Output:

0 1 2 3 3 5 7 8 12 12 12 23 34 66 87