CODEWITHSUNDEEP
javascriptarrays
billygreen
billygreen

Reputation: 223

Making a function returning assorted arrays?

I am trying to define a function, merge, which, when given two sorted arrays containing numbers, returns a sorted array of the numbers from both lists.

merge([ 4, 5, 6 ], [ 1, 2, 3, 4 ]) => [ 1, 2, 3, 4, 4, 5, 6 ]
merge([ 4 ], [ 2, 5, 8 ]) => [ 2, 4, 5, 8 ]
merge([ 1, 2, 6 ], []) => [ 1, 2, 6 ]

This is my code: 

function merge(arr1, arr2) {
  return arr1.concat(arr2).sort(arr1, arr2);
}

While the output is correct, I am told -- from my studies, and its automated tests -- that this code is not in good style. It writes:

Does not handles two arrays of same length.

Doesn't handle shorter first array.

Doesn't handle shorter second array.

What is a better way I can write this code? What should I do better?

Upvotes: 1

Views: 239

Answers (4)

ggorlen
ggorlen

Reputation: 56875

Amadan's answer paid attention to the problem constraints and pointed out that this can be written in O(n) time. Essentially, when inputs are both sorted, the algorithm is the "merge" step in a merge sort. This is done in linear time and works in a very simple and pleasing manner: look at the first item of each list and take the smaller of the two until one or both lists are exhausted. Then, tack any remaining elements onto the result array and return it.

The other answers are fine and in good JS style, but are in O(n log n) time and ignore entirely that the arrays are pre-sorted without mention, which is almost certainly not the answer someone asking for this routine would be looking for.

Here's a merge step:

const merge = (a, b) => {
  const result = [];

  while (a.length && b.length) {
    result.push(a[0] < b[0] ? a.shift() : b.shift());
  }

  return result.concat(a).concat(b);
};

console.log(merge([ 4, 5, 6 ], [ 1, 2, 3, 4 ])); // => [ 1, 2, 3, 4, 4, 5, 6 ]
console.log(merge([ 4 ], [ 2, 5, 8 ])); // => [ 2, 4, 5, 8 ]
console.log(merge([ 1, 2, 6 ], [])); // => [ 1, 2, 6 ]

This can also be done with indexes which preserves the original arrays and is faster, but a little uglier-looking.

Here's a benchmark at JSPerf.

benchmark

Upvotes: 3

Amadan
Amadan

Reputation: 198324

Other answers already give you the literal answer of how to make your code correct. However, it is possibly missing the point. The function that you described is used in building a "merge sort", a very important sorting algorithm, whose major advantage is that it only needs to read the input lists once, sequentially, resulting in complexity of O(N) per pass; this allows it to even sort things that can't fit into the memory. Your code does not do that - it relies on sort, which is O(N log(N)) each time you invoke your function, and it doesn't utilise the fact that both its inputs are already pre-sorted (which is a key requirement for merge sort).

The merge sort algorithm will take the first element from both lists, then append the smaller one. Then it compares the next element from that list with the other list's first element, and again takes the smaller one. Repeat until one list is exhausted, then append the rest of the surviving list. (You can find a more exhaustive explanation of the merge sort on the Wikipedia page).

Upvotes: 3

Tom O.
Tom O.

Reputation: 5941

Just concat the arrays and return after applying a simple sort function: 

console.log(merge([4, 5, 6], [1, 2, 3, 4])); //[ 1, 2, 3, 4, 4, 5, 6 ]

console.log(merge([4], [2, 5, 8])); //[ 2, 4, 5, 8 ]

console.log(merge([1, 2, 6], [])); //[ 1, 2, 6] 


function merge(a, b) {
  return a.concat(b).sort((a, b) => a - b);
}

Upvotes: 1

Dacre Denny
Dacre Denny

Reputation: 30360

Your code looks ok, however the way you're using sort is incorrect. One way to use sort is to supply a function that compares two values in the array, and returns a number (positive or negative) to dictate the sorting of those values. For more information on sort, see this article

Consider the following changes to your merge method:

function merge(arr1, arr2) {
  return arr1.concat(arr2).sort(function(valueA, valueB) { return valueA - valueB; );
}

Upvotes: 3

Related Questions