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.

  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.
  //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));
    //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));
    //Default: Uh-oh

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.


1 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:

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

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

  while (moreNumbers()) {
    let nextNumber = getNextNumber();
    if (!inFilter(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] ) {
        return nextNumbers[0];
      } else if (nextNumbers[0] > nextNumbers[1] ) {
        return nextNumbers[1];
     } else { // Both arrays have the same number
        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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.