How to merge sorted arrays within arrays into a third sorted array

Question

The title may be confusing and forgive me as I am still a beginner. This is part of a HW assignment for school and although I am not looking for the answer outright I need a push in the right direction, or any help at all. So onto the question...

I need to create a simple program based on the code in class to merge multiple sorted arrays into one sorted array to output to the screen. The arrays are hardcoded in as "test cases" to uncomment and verify. The instuctors directions are as follows

Using the merge program developed in class (see attached) as a base, create a version that will merge 0 (zero) to n arrays of numbers. Hints: Sort the arrays before merging Use the shift method to remove the first item in an array (arrayName.shift()) To create an array of arrays ---> var x = [ ]; var y = [ ]; var z = [ x, y ];

EDIT: I have emailed the instructor with a solution based on the answer given by @cpugourou and his reply was that he will not accept that solution. The point of the homework is to manually merge these arrays.

Below is the original "Merge Program" that we developed in class

"use strict";   // reduces chance for error

/* 
    there are 2 arrays here and this program will merge them.
    Your job is to merge zero or more arrays. Test cases include:
    1. arrays with no elements: x = [], y = [], z = [], ...
    2. 2 arrays - one with elements and one without: x = [], y = [200, 39,1]
    3. 4 arrays: x = [5, 1, 0], y = [], z = [78, 3], w = [4, 34]
*/
var x = [ 12, 5, 1], y = [ 13, 2, 3], z = [];   // x and y are input and, after processing, z has the merged arrays
var ix = 0, iy = 0, iz = 0;         // indexes to the next element

// The following sorts the arrays in ascending sequence
x.sort(function(a, b){return a - b});
y.sort(function(a, b){return a - b});

while (ix < x.length || iy < y.length){     // while arrays x or y have elements

if (ix < x.length && iy < y.length){    // if both have elements, choose the lowest element

    if (x[ix] <= y[iy]){                // is the current element in array x less than the current element in y?
        z[iz] = x[ix];                  // choose x
        iz++;                           // point to the next space in z
        ix++;                           // ditto x
    } else{                             // choose y
        z[iz] = y[iy];                  
        iz++;                           // next
        iy++;                           // next
    }

} else if (ix < x.length){              // if only one has elements is it x?
    for (ix; ix < x.length; ix++){      // if so, move the rest of x to z
        z[iz] = x[ix];                  // copy current element in x
        iz++;                           // next z ... no need to increment x because the for loop does it
    }

} else if (iy < y.length){              // if only y has elements
    for (iy; iy < y.length; iy++){      // move the rest of y to z
        z[iz] = y[iy];                  // copy
        iz++;                           // increment z's pointer
    }
}
}

// display the resulting merged elements in the web page
var result = "<ul>";
for (var i in z){
    result += "<li>" + z[i] + "</li>"
}
result += "</ul>"
document.getElementById("placeAnswerHere").innerHTML=result;

/*
Things to think about:
. This code is hard wired to merge only 2 arrays
. You will need to create an array containing all arrays to be merged. e.g. q = [x, y, z, w, and more]
. Your loop will need to find the smallest element in any of the arrays in q and move it to z (the resultant array)
. There is a method shift() to strip the first element from an array (e.g. x.shift(); removes the first element in array x)
. This is like making a pile of cafeteria trays from a variable numbers of tray stacks.
. Remember to sort all arrays first
*/

So my new question becomes, how to accomplish this without writing a bunch of spaghetti code?

Answer 1

Although cpugourou's answer works, it doesn't appear to match the stated HW assignment. As for the HW assignment, one issue not clear to me is how to create a generic array of arrays (like for(i = 0; i < n; i++) aa[i] = new Array(...) ), which seem to conflict with the HW problem statement that the arrays are hard coded test cases.

Ignoring the issue of how to create generic array of hard coded arrays, once you do have an array of sorted arrays, the HW assignment appears to want you to implement an n way merge using the array of arrays. This means finding which array in the array of arrays has the smallest element and moving that element to the output array (append to output array, remove from the input array). When one of the n arrays is emptied, that array is removed from the array of arrays and you continue with an n-1 way merge. Repeate this until only 1 array remains, where the remainder of that last array is just copied (or moved) to the output array.

A common optimization for a n way merge is to use a heap, but I doubt you're expected to use a heap for this HW assignment.

Answer 2

the fastest and shortest I can think of (unduplication bonus added):

var x = [5, 1, 0], y = [2, 5, 0], z = [78, 3, 1], w = [4, 34];

function sortNumber(a,b) {
    return a - b;
}
function uniq(a) {
   return Array.from(new Set(a));
}

var d = uniq(x.concat(y,z,w).sort(sortNumber));
/* [0, 1, 2, 3, 4, 5, 34, 78] */