Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique

Question

The code below was taught in my Data Structures and Algorithms class. I am currently reviewing it in preparation for exams. The code, by the lecturer, works well.

#include<iostream>
#define size 34
using namespace std;

int i,j,n;
int array[size];

void getvalues(){
    cout<<"how many values ";
    cin>>n;
    cout<<"enter values ";
    for(i=0; i<n; i++){
        cin>>array[i];
    }
}
void display(){
    for(i=0; i<n; i++){
        cout<<array[i]<<"  ";
    }
}

void merge(int array[], int low, int mid, int high){
    i=low; //low of first half
    j=mid+1; //low of second half 
    int k=low; // LOW for temporary new sorted array that we will form
    int temp[n];
    
    // Its like while low of each list <= high
    while(i<=mid && j<=high){  //?????????????????????????????
        // if array at i < array at j...
        if(array[i] < array[j]){
            temp[k] = array[i]; // set array at k to be equal to array at i
            i++; //move foward by one
            k++; //move foward byone
            
        } 
        else // if array at j < array at i...
        {
            temp[k]=array[j]; // set array at k to be equal to array at j instead
            k++; //move foward by one
            j++; //move foward by one
        }
            
    }
    
    //mop remaining values
    while(i<=mid){
        temp[k]=array[i];
            i++;
            k++;    
    }
    
    while(j<=high){
        temp[k]=array[j];
            k++;
            j++;
    }
    //copy to original array
    for(i=low; i<k; i++)
    array[i]=temp[i];
}

void mergesort(int array[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        // Split the data into two half.
        mergesort(array, low, mid);
        mergesort(array, mid+1, high);
 
        // Merge them to get sorted output.
        merge(array, low, mid, high);
    }
}

 
 int main(){
    getvalues();
    mergesort(array, 0, n-1);
    display();
}

However, I do not understand the purpose of the last 2 while loops within the merge (not mergesort) function. I thought just 1 would be enough.

Could someone kindly explain to me why we need 2 extra while loops?

Help with testing I also need help on how to test the result after the first while loop is exited. How can I print that result? I have tried using the display() function amongs other methods that return weird results or simply do not work. May I also get help with that?

Below is the "weird result" I get after trying to use display to print after the first while loop in merge function. It even results in a distortion of the result since the array is not sorted. How can I test-print in c++?

running the program after test-printing

Answer 1

Initialization: We have two sorted arrays, A and B, and we're merging them into a single sorted array, C.

The idea of ​​the merge function is:

1.We iterate through both arrays simultaneously using two indexes, one for each array. While both arrays have elements remaining, we compare the elements at the current index. The smaller element is appended to the combined array, C. We increase the index of the array from which we took the smaller element and increase the index of array C.

2. if array A reaches its end before B array, we know that the remaining elements in the other array are already sorted. Therefore, we simply copy the remaining elements from that array into C. This is done in a separate loop after the main merge loop.(this is the second while loop)

3. The third while loop does the same as 2 but checks the opposite. (if B reaches the end before A ).

hope i helped, good luck in your exam!

Answer 2

Only one of the two loops will be run (the other will loop zero times). This is easier to understand if the code to handle end of run is included in each part of the if | else compare logic in the merge function.

A one time allocation of the second array and one time copy at entry to merge sort and then alternating the direction of merge with each level of recursion eliminates the need for a copy back in Merge. The code below is C or C++ code (it uses malloc instead of new), the range of data is [bgn, end) instead of [low, high], where end is 1+index to the last element, which is more common in the case of merge sort.

void Merge(int a[], int bgn, int mid, int end, int b[])
{
int i, j, k;
    i = bgn, j = mid, k = bgn;
    while(1){
        if(a[i] <= a[j]){               // if left smaller
            b[k++] = a[i++];            //  copy left element
            if(i < mid)                 //  if not end of left run
                continue;               //    continue
            do                          //  else copy rest of right run
                b[k++] = a[j++];
            while(j < end);
            break;                      //   and break
        } else {                        // else right smaller
            b[k++] = a[j++];            //  copy right element
            if(j < end)                 //  if not end of right run
                continue;               //    continue
            do                          //  else copy rest of left run
                b[k++] = a[i++];
            while(i < mid);
            break;                      //   and break
        }
    }
}

void MergeSortR(int b[], int bgn, int end, int a[])
{
    if (end - bgn <= 1)                 // if run size == 1
        return;                         //   consider it sorted
    int mid = (end + bgn) / 2;
    MergeSortR(a, bgn, mid, b);
    MergeSortR(a, mid, end, b);
    Merge(b, bgn, mid, end, a);
}

void MergeSort(int a[], int n)          // n = size (not size-1)
{
    if(n < 2)
        return;
    int *b = (int *) malloc(n*sizeof(int)); // 1 time allocate and copy
    for(size_t i = 0; i < n; i++)
        b[i] = a[i];
    MergeSortR(b, 0, n, a);             // sort data from b[] into a[]
    free(b);
}

Link to Wikipedia article showing the same logic:

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation