basic MergeSort exercise

Question

Requirement: Based on the code provided below, implement the merge sort algorithm to rearrange an array with N elements. While running the algorithm, print array A after each merge of two subarrays.

Input

• The first line is a positive integer N (0 < N < 20)
• The next line contains N integers Who are the elements of the array

Output

• The next lines print out the configuration of array A.

Example:

Input

10

800 728 703 671 628 625 518 508 392 331

Output

[ 728 800 ] 703 671 628 625 518 508 392 331

[ 703 728 800 ] 671 628 625 518 508 392 331

703 728 800 [ 628 671 ] 625 518 508 392 331

[ 628 671 703 728 800 ] 625 518 508 392 331

628 671 703 728 800 [ 518 625 ] 508 392 331

628 671 703 728 800 [ 508 518 625 ] 392 331

628 671 703 728 800 508 518 625 [ 331 392 ]

628 671 703 728 800 [ 331 392 508 518 625 ]

[ 331 392 508 518 625 628 671 703 728 800 ]

I'm having trouble finding a way to print out the remaining elements of the array after each merge. this is my code, hope any one can help me:

#include <iostream>

using namespace std;

void printArray(int arr[], int start, int end) {
    cout << "[ ";
    for (int i = start; i <= end; ++i) {
        cout << arr[i];
        if (i < end) {
            cout << " ";
        }
    }
    cout << " ] ";
}

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = new int[n1];
    int* R = new int[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;
    }

    // In ra mảng sau mỗi lần trộn hai mảng con
    printArray(arr, left, right);
    cout << endl;

    delete[] L;
    delete[] R;
}

void mergeSort(int 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);
    }
}

int main() {
    int N;
    cin >> N;

    int* arr = new int[N];
    for (int i = 0; i < N; ++i)
        cin >> arr[i];

    mergeSort(arr, 0, N - 1);

    delete[] arr;

    return 0;
}

After running my code, this is the output of example :

[ 728 800 ]

[ 703 728 800 ]

[ 628 671 ]

[ 628 671 703 728 800 ]

[ 518 625 ]

[ 508 518 625 ]

[ 331 392 ]

[ 331 392 508 518 625 ]

[ 331 392 508 518 625 628 671 703 728 800 ]

As you can see, this is not contain the entire array but only print the elements already be merged, i want it look like the output example.

Answer 1

The underlying problem is that printArray is not designed to print the entire array. It only knows to print the elements between start and end. It has no idea to print the elements before start, and the elements after end.

For printArray to print all of the elements, you must pass the information to printArray that there are N elements in total, not just start and end. Once that's done, then all printArray needs to do is

1. Print the elements before start.
2. Print the elements between start and end.
3. Print the elements after end.

The simplest way to do this is add an extra argument to the merge, mergeSort and printArray function that denotes the number of elements in the array:

1. void merge(int arr[], int left, int mid, int right, int numElements)

2. void mergeSort(int arr[], int left, int right, int numElements)

3. void printArray(int arr[], int start, int end, int numElements)

In main, you would call mergeSort like this:

mergeSort(arr, 0, N - 1, N);

and all the calls to mergeSort, merge and printArray would pass the value of numElements, eventually ending up in printArray.

Then for printArray, the function is very simple:

void printArray(int arr[], int start, int end, int numElements) {
    
    for (int i = 0; i < start; ++i)
        std::cout << arr[i] << " ";

    cout << "[ ";
    for (int i = start; i <= end; ++i) {
        cout << arr[i];
        if (i < end) {
            cout << " ";
        }
    }
    cout << " ] ";

    for (int i = end + 1; i < numElements; ++i)
        std::cout << arr[i] << " ";
}

Live demo