Implement the merge sort + binary search algorithms to filter and merge sort two arrays

Question

I wanted to take my own shot at a merge sort array implementation. I took on the prompt from Rahul's post.

The goal (altered a little for my purposes):

Implement a solution capable of merging & sorting two arrays (already in ascending order) as well as filtering out values from a 3rd array.

I based the merge sort algorithm on what I read on Wiki and the binary sorting algorithm on what I read on Khan Academy.

    /*
  I was reading through a post from earlier - "If given two sorted arrays where first containing -1, merge into one sorted array" - https://codereview.stackexchange.com/questions/156963/if-given-two-sorted-arrays-where-first-containing-1-merge-into-one-sorted-arra

  The first thing that I noticed is that OP didn't mention if he/she was using any algorithms, so I thought I would see if there were any out there that seemed like they might be a good fit for this.

  So, I took off in the Google Mobile.  I just searched for "merge sorted array".  I found that there is something called the "merge sort algorithm".  Cool.
  https://en.wikipedia.org/wiki/Merge_algorithm

  So this is my attempt at a merge sort algorithm.  I'm not actually sure if the post that lead me to this implmemented it or not.

  As always, I will attempt to follow the SMoRES principles:
  Scalable: Does the code scale to N+1? - What if I want to merge more than 2 arrays or filter more than 1 number?
  Modular - Is the code modular?  Can I change the bits and peices of the code without breaking it?
  Extensible - Can I add to the code without an entire restructure?
  Simple? - Have I kept the code simple where I can?
*/

/*Goal: merge two sorted arrays and filtering those values based on a filter array.*/


console.log(filterAndSort([ [3,6,-1,11,15,-1,32,34,-1,42,-1], [1,3,10,17,56] ], [-1,0]));

// console.log(removeFirstElement([1,2,3]));

function filterAndSort(arraysToMerge, filterArray){
  var sortedArray = []; //Initialize return array
  var manageArrays = [[],[]]; //Initialize the return arrays
  var arraySelector = 0;
  //Loop through the arrays being merged
  while (arraysToMerge[0].length > 0 && arraysToMerge[1].length > 0){
    //Push the number from the first of the two arrays being sorted
    if (arraysToMerge[0][0] < arraysToMerge[1][0]) {
      arraySelector = 0;
    }
    //Push the number from the second of the two arrays being sorted
    else if (arraysToMerge[0][0] > arraysToMerge[1][0]){
      arraySelector = 1;
    }
    //Push the number from the first of the two arrays being sorted, pop from the second to avoid repeated numbers
    else {
      arraySelector = 0;
      arraysToMerge[1] = removeFirstElement(arraysToMerge[1]);
    }
    //Update the arrays
    manageArrays = setArrays([sortedArray, arraysToMerge[arraySelector]], filterArray);
    arraysToMerge[arraySelector] = manageArrays[1];
    sortedArray = manageArrays[0];
  }
  while (arraysToMerge[0].length > 0){
    manageArrays = setArrays([sortedArray, arraysToMerge[0]], filterArray);
    arraysToMerge[0] = manageArrays[1];
    sortedArray = manageArrays[0];
  }
  while (arraysToMerge[1].length > 0){
    manageArrays = setArrays([sortedArray, arraysToMerge[1]], filterArray);
    arraysToMerge[1] = manageArrays[1];
    sortedArray = manageArrays[0];
  }
  //console.log("Done! " + sortedArray);
  return sortedArray;
}

//For modularity, let's create a delete function
function removeFirstElement(array){
  var updatedArray = array.splice(1);
  return updatedArray;
}

//For modularity, let's create a get first element function
function getFirstElement(array){
  var element = array[0];
  return element;
}

//For modularity, let's create a set function for the final array
function setArrays(arraysToEdit, filterArray){
  //Get the elemement at the front of the array being sorted
  var number = getFirstElement(arraysToEdit[1]);
  //Check to see if we need to filter the number
  if (filterNumber(number, filterArray)){
    //Append the number onto the back of the sorted array.
    arraysToEdit[0].push(number);
  }
  //Pop the number off the array being sorted.
  arraysToEdit[1] = removeFirstElement(arraysToEdit[1]);
  //Return the edited arrays
  return arraysToEdit;
}

//This is a repeated task - returns a number correllating the comparison between the number and the value of an array @ a particular index.
function compareValues(number, numAtIndex){
  if (number == numAtIndex){return 1;}
  else if(number > numAtIndex){return 2;}
  else if (number < numAtIndex) {return 3;}
  else {return 0;}
}

//Implements a binary search, returns 0 (filter) or 1 (Do not filter)
function filterNumber(number, filterArray){
  //Step 1: Find the size of the array
  var index = Math.floor(filterArray.length/2);
  switch (compareValues(number, filterArray[index])) {
    //Case 1: We need to filter the number
    case 1:
      return 0;
    //Case 2: Check the right side of the array
    case 2:
      if (index + 1 >= filterArray.length){return 1;}  //Reached the end!
      //Pare down the array.
      else {
        filterNumber(number, filterArray.slice(index));
        break;
      }
    //Case 3: Check the left side of the array
    case 3:
      if (index - 1 < 0){return 1;} //Reached the end!
      //Pare down the array.
      else {
        filterNumber(number, filterArray.slice(0, index));
        break;
      }
    //Default: Uh-oh
    default:
      break;
  }
}

This took about 0.08 seconds to run in Atom on a MacBook Pro from 2013 - except on the first run. The first run always takes almost 2 seconds in Atom. I'm not sure how to correctly benchmark code timing.

Answer 1

A couple of points:

• I wouldn't be too surprised by the initial run time. The JavaScript compiler has to load and parse the code. It also uses the results of the first run to optimize itself.

• function setArrays(arraysToEdit, filterArray) : Why not pass 3 parameters (sortedArray, arrayToMerge and filterArray) instead of making the first parameter an array of arrays? It would make the code easier to read.

• function removeFirstElement(array) : Array modification is very expensive. Rather than removing elements all the time, which is potentially expensive, use an index variable to track where you where.

• function compareValues(number, numAtIndex) : It is kind of a standard in JavaScript is to use 1, 0 and -1 as comparison values (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description). Also it doesn't seem that you need to be handling the last else. If that is an uh-oh kind of bug then find it and fix it.

I would do something like:

console.clear();
var results = filterAndSort([ [3,6,-1,11,15,-1,32,34,-1,42,-1], 
                              [1,3,10,17,56] ], 
                            [-1,0] );
console.table(results);                            

function filterAndSort(arraysToMerge, filterArray) {
  let mergeIndexes = new Array(arraysToMerge.length).fill(0),
      results      = [];

  while (moreNumbers()) {
    let nextNumber = getNextNumber();
    if (!inFilter(nextNumber))
      results.push(nextNumber);
  }

  return results;

  // It should be easy to modify this to handle an arbitrary number of arrays  
  function getNextNumber() {
      let nextNumbers  = [ getNextElement(0),
                           getNextElement(1) ];

      if (nextNumbers[0] < nextNumbers[1] ) {
        mergeIndexes[0]++;
        return nextNumbers[0];
      } else if (nextNumbers[0] > nextNumbers[1] ) {
        mergeIndexes[1]++;
        return nextNumbers[1];
     } else { // Both arrays have the same number
        mergeIndexes[0]++;
        mergeIndexes[1]++;
        return nextNumbers[0];
      }
  }  

  function getNextElement(index) {
    let position = mergeIndexes[index];
    if (position < arraysToMerge[index].length) {
      return arraysToMerge[index][position];
    } else {
      return Number.MAX_VALUE;
    }
  }

  function moreNumbers() {
    return mergeIndexes[0] < arraysToMerge[0].length ||
           mergeIndexes[1] < arraysToMerge[1].length;
  }

  function inFilter(number) {
    let first = 0, last = filterArray.length-1;

    while (first <= last) {
      let index = (first+last) >> 1;
      let numAtIndex = filterArray[index];
      if (number > numAtIndex)  {
        first = index + 1;
      } else if (number < numAtIndex)  {
        last = index - 1;
      } else { // number === numAtIndex
        return true;
      }
    }
    return false;
  }

}

Note: I defined the helper functions inside the merge function to make them private.