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

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.

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.