Merge Sort Demo (C++)

[Qingquan-Li]

#include <iostream>

/**
 * Merge two sorted sub-arrays into one sorted sub-array
 * @param arr: the array to be sorted
 * @param first1: the index of the first element of the first sub-array
 * @param last1: the index of the last element of the first sub-array
 * @param first2: the index of the first element of the second sub-array
 * @param last2: the index of the last element of the second sub-array
 * @return: void
 * @precondition: the two sub-arrays are sorted
 * @postcondition: the two sub-arrays are merged into one sorted sub-array
 * @time complexity: O(n)
 * @space complexity: O(n)
 * @see mergeSort
 */
void merge(int arr[], int first1, int last1, int first2, int last2)
{
    int size = (last2 - first1) + 1; // Size of the merged sub-array. the first index is 0
    int *temp = new int[size];       // Temporary array to store the merged sub-array

    int current = 0; // Index of the temporary array
    int i = first1;  // Index of the first sub-array
    int j = first2;  // Index of the second sub-array

    // Compare the elements of the two sub-arrays and merge them in sorted order
    while (i <= last1 && j <= last2) // While there are elements in both sub-arrays to be merged
    {
        if (arr[i] <= arr[j])        // If the element in the first sub-array is smaller than
                                     // the element in the second sub-array
        {
            temp[current] = arr[i];  // Copy the element in the first sub-array to the temporary array
            i++;                     // Increment the index of the first sub-array
        }
        else
        {
            temp[current] = arr[j];  // Copy the element in the second sub-array to the temporary array
            j++;                     // Increment the index of the second sub-array
        }
        current++;                   // Increment the index of the temporary array
    }

    // If there are any remaining elements in the first subarray, copy them
    while (i <= last1)          // While there are elements in the first sub-array to be merged
    {
        temp[current] = arr[i]; // Copy the element in the first sub-array to the temporary array
        i++;                    // Increment the index of the first sub-array
        current++;              // Increment the index of the temporary array
    }

    // If there are any remaining elements in the second subarray, copy them
    while (j <= last2)          // While there are elements in the second sub-array to be merged
    {
        temp[current] = arr[j]; // Copy the element in the second sub-array to the temporary array
        j++;                    // Increment the index of the second sub-array
        current++;              // Increment the index of the temporary array
    }

    // Copy the merged elements back into the original array
    for (i = first1, current = 0; i <= last2; i++, current++)
    {
        arr[i] = temp[current]; // Copy the element in the temporary array to the original array
    }

    delete[] temp; // Free the memory allocated for the temporary array
}

/**
 * Sorts an array using merge sort, a divide and conquer algorithm, recursively
 * @param arr: the array to be sorted
 * @param first: the index of the first element of the array
 * @param last: the index of the last element of the array
 * @return: void
 * @precondition: the array is not empty
 * @postcondition: the array is sorted in ascending order
 * @time complexity: O(nlogn)
 * @space complexity: O(n)
 * @see merge
 */
void mergeSort(int arr[], int first, int last)
{
    if (first < last) // If there is more than one element in the array
    {
        int middle = (first + last) / 2;  // Index of the middle element
        mergeSort(arr, first, middle);    // Sort the first half of the array
        mergeSort(arr, middle + 1, last); // Sort the second half of the array
        merge(arr, first, middle, middle + 1, last);
    }
}

int main() {
    int n;

    // Ask user for the size of the array
    std::cout << "Enter the size of the array: ";
    std::cin >> n; // 8

    int* arr = new int[n];

    // Ask user for array elements
    std::cout << "Enter the elements of the array (separated by spaces): ";
    // 90 42 15 60 80 30 7 5
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    // Sort the array
    mergeSort(arr, 0, n - 1);

    // Print the sorted array
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    // 5 7 15 30 42 60 80 90

    delete[] arr;
    return 0;
}

Enter the size of the array: 8
Enter the elements of the array (separated by spaces): 90 42 15 60 80 30 7 5
Sorted array: 5 7 15 30 42 60 80 90