How to print the left and right sub-array before displaying the final merge sorted array?

Question

This is what I have so far https://notepad.vn/lvqrsmz99

#include<stdlib.h> 
#include<stdio.h> 
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 

    int L[n1], R[n2]; 

    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

    i = 0;  
    j = 0; 
    k = l; 
    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++; 
    } 
} 
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        int m = l+(r-l)/2; 

        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 

        merge(arr, l, m, r); 
    } 
} 

void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 

int main() 
{ 
    int arr[20];
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
      scanf("%d",&arr[i]);
    }
    printArray(arr, n); 
    mergeSort(arr, 0, n - 1); 
    printf("\nSorted array is \n"); 
    printArray(arr, n); 
    return 0; 
} 

This is what I need to print prior the final sorted array:

3

14

3 14

1

12

5

1 3 14

5 12

Answer 1

Noobie, there is a pretty good hint about where the "merge" is taking place in your code. That would provide a perfect place to look at the left and right sub-arrays before the merge.

If you look at the merge() function, you see the left and right sub-arrays being populated in the following code:

    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 

With a little creativity, you could output the sub-arrays as they are being filled to obtain your desired output, e.g.

    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
        printf (" %d", L[i]); 
    }
    putchar ('\n');
    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j]; 
        printf (" %d", R[j]); 
    }
    putchar ('\n');

(you could even add an additional putchar ('\n'); after your first call to printArray (arr, n); to format the output a bit nicer)

Example Use/Output

When implemented, your output would be:

$ echo "5 3 14 1 12 5" | ./bin/mergeprn
3 14 1 12 5

 3
 14
 3 14
 1
 12
 5
 1 3 14
 5 12

Sorted array is
1 3 5 12 14

(the input values were gleaned from your question)

Other Issues

Don't use magic numbers in your code (except where absolutely required like with the scanf field-width modifier). Instead, If you need a constant, #define one (or more), or use a global enum to do the same thing. That way you have one single place at the top of your code to change things if needed and you don't have to go picking through your declarations or loop limits to change things. E.g.

#define MAXA 20
...
    int arr[MAXA] = {0};    /* always initialize arrays */

Always Validate scanf Return

Any time you are using scanf you must validate the return or you are just asking for Undefined Behavior in the event of a matching or input failure. It doesn't take much more effort, but will save you a world of grief, e.g.

    if (scanf ("%d", &n) != 1) {
        fputs ("error: invalid array size\n", stderr);
        return 1;
    }
    if (n > MAXA) {  /* protect your array bounds */
        fprintf (stderr, "error: array size exceeds bound '%d'\n", MAXA);
        return 1;
    }
    if (n < 2) {     /* make sure you have something to sort */
        fputs ("error, 'n' less than 2, nothing to sort\n", stderr);
        return 1;
    }

    for (i = 0; i < n; i++)
        if (scanf ("%d", &arr[i]) != 1) {
            fprintf (stderr, "error: invalid input 'arr[%d]'\n", i);
            return 1;
        }

Now you can rest assured you are processing valid input, and not some accidental character that causes a matching failure and Undefined Behavior in your code.