How is this sorting the array in Java during merge [closed]

Question

I was just reviewing some merge sorting and finding that I'm missing how when merging it is storing the sorted arrays.

import java.util.Arrays;

public class MergeTwoArrays2 {
  public static void main(String[] args) {

    int a[] = { 10, 20, 30 };
    int b[] = { 40, 50, 60, 70, 80 };

    // determining length of both arrays
    int a1 = a.length;
    int b1 = b.length;

    // resultant array size
    int c1 = a1 + b1;

    // Creating a new array
    int[] c = new int[c1];

    // Loop to store the elements of first
    // array into resultant array
    for (int i = 0; i < a1; i = i + 1) {
      
        // Storing the elements in 
        // the resultant array
        c[i] = a[i];
    }

    // Loop to concat the elements of second 
    // array into resultant array
    for (int i = 0; i < b1; i = i + 1) {

        // Storing the elements in the 
        // resultant array
        c[a1 + i] = b[i];
    }

    System.out.println("" + Arrays.toString(c));
}
}

Answer 1

You are asking two different questions.

The first:

How is this sorting the array in Java during merge

It isn't doing any sorting at all. The two arrays have already been sorted.

The second:

I was just reviewing some merge sorting and finding that I'm missing how when merging it is storing the sorted arrays.

Now you recognize the arrays are already sorted. The answer is that it isn't merging anything. It is simply copying each array, back to back to another array.

A merge would take two different sorted arrays, and iterate across both comparing values from each to obtain their proper position in the final array relative to each other.

A real merge algorithm would work if arrays a and b traded places. In your code it wouldn't and the result would be [40, 50, 60, 70, 80, 10, 20, 30]

Answer 2

The algorithm isn't doing merge sorting. It just concatenates two arrays, a[] and b[], in your case. You are getting the resulting array as sorted because all elements in your array are sorted. If you put in some random numbers in between and disturb the order, the result won't be sorted anymore.

For ex: if I had a = {100, 10, 1} b = {20, 40, 60} then c would be {100, 10, 1, 20, 40, 60}

Answer 3

Your method works perfectly if both arrays are sorted, and the highest value contained in the items of the first is less than the lowest value of the items contained in the second, but what if this is not the case?, let's see how to do it if both arrays are sorted, but do not meet the second condition:

int a[] = { 10, 20, 50 };
int b[] = { 5, 25, 35, 70, 80 };

  // put the code in a method
int[] mergeArrays( int arrA[], int arrB[] ) { 
      int size = arrA.length + arrB.length;
      int[] out = new int[ size ];
      int indexA = 0, indexB = 0;
      System.out.println( size );
      for( int i = 0; i < size; i ++ ) {
         if( indexA >= arrA.length  ) {
            out[ i ] = arrB[ indexB ++ ];
         }
         else if( indexB >= arrB.length ) {
            out[ i ] = arrA[ indexA ++ ];
         }
         else if( arrA[ indexA ] < arrB[ indexB ] ) {
            out[ i ] = arrA[ indexA ++ ];
         }
         else {
            out[ i ] = arrB[ indexB ++ ];
         }
      }
      // because "Arrays.toString" return a string, delete "" +
      System.out.println( Arrays.toString( out ) );
      return out;
}

Inside the for, in the first iteration, first we check if indexA or indexB have a value greater than the length of the respective array, in which case, we assign out the corresponding value of the other, if not and the condition of the first if is not met, so the code in the else is executed, assigning to out the value contained in the first position of arrB ("5"), but also modifies the value of indexB with the statement arrB[ indexB++ ], with ++ being responsible for that change.

In the next iteration, it no longer compares the first item of arrA with the first item of arrB because indexB now equals "1", so the condition is met and its code is executed, until it finishes.

Tomorrow I will add the case of both arrays being unordered.