Sorting two non-sequential arrays to one array ascending

Question

I was trying to sort two arrays with non sequential numbers into one array after I did with sequential numbers. Do I need to order the arrays separately or is there a more effective way?

If I run the code below my output will be 4,16,2,11,19.. and it should be 0,1,2,3,4..

    int myFirstArray [] = { 16, 2, 11, 34, 77, 1, 0, 10, 3 };
    int mySecondArray [] = { 4, 19, 6, 32, 8, 10, 66 };
    int firstPos = 0, secondPos = 0;

    int myThirdArray [] = new int[myFirstArray.length + mySecondArray.length];

    for (int i = 0; i < myThirdArray.length; i++) {
        if (firstPos < myFirstArray.length && secondPos < mySecondArray.length) {
            if (mySecondArray[secondPos] < myFirstArray[firstPos]) {
                myThirdArray[i] = mySecondArray[secondPos];
                secondPos++;
            }
            else {
                myThirdArray[i] = myFirstArray[firstPos];
                firstPos++;
            }       
        }
        else if (secondPos < mySecondArray.length) {
            myThirdArray[i] = mySecondArray[secondPos];
            secondPos++;
        }
        else {
            myThirdArray[i] = myFirstArray[firstPos];
            firstPos++;
        }
    }

    for(int i = 0; i < myThirdArray.length; i++) {
        System.out.println(myThirdArray[i]);
    }

Answer 1

If you had 2 sorted arrays and want to combine them into one sorted array then your code would be correct. But you are comparing the first 2 elements of your unsorted arrays and create a topically sorted array, meaning some elements of the array are sorted compared to others ie 4 < 16, 2 < 11 < 19.

Your logic is not far away from Mergesort. You split your array into halves and split them again and merges the 2 halves. You end up merging arrays of size 1, then merging arrays of size 2 and so on and so on. Your merging code is correct. You can see more details here.

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[l + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[m + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Find the middle point
        int m = (l+r)/2;

        // Sort first and second halves
        sort(arr, l, m);
        sort(arr , m+1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}