Recursive merge sort function error: Cannot read property 'length' of undefined

Question

I am working on writing my own recursive merge sort function from scratch in javascript, but any time I test it with any array of numbers I receive the following error: "TypeError: Cannot read property 'length' of undefined"

I have no idea why I am receiving this error since the only places I use the "length" property are on my argued arrray (within the mergeSort function) and on subarrays of this array (within the merge function). My merge function already works perfectly when tested on its own when given two sorted arrays of any length.

Here is my entire code:

function merge(arrayOne, arrayTwo){
  let sorted = []
  while(arrayOne.length > 0 && arrayTwo.length > 0){
    if(arrayOne[0] < arrayTwo[0]){
      sorted.push(arrayOne.shift());
    } else{
      sorted.push(arrayTwo.shift());
    }
  }
  return sorted.concat(arrayOne).concat(arrayTwo);
}

function mergeSort(array){
  let arrayLength = array.length;
  let midpoint = arrayLength/2;
  let firstHalf = array.slice(0, midpoint);
  let secondHalf = array.slice(midpoint, arrayLength);
  if(arrayLength < 2){
    return array;
  } else{
    merge(mergeSort(firstHalf), mergeSort(secondHalf));
  }
}

With the given code, the only place you use length is while(arrayOne.length > 0 && arrayTwo.length > 0){ Your error, cannot read length of undefined, so arrayOne and/or arrayTwo is undefined — Huangism
– Huangism, Commented Jul 10, 2017 at 18:20

Damon · Accepted Answer · 2017-07-10 18:32:32Z

Edit Looks like you defined arrayLength in an edit, so the only outstanding issue is that you must return merge(...) at the end of mergeSort

Here is a fixed version of the algorithm:

function merge(arrayOne, arrayTwo){
  let sorted = []
  while(arrayOne.length > 0 && arrayTwo.length > 0){
    if(arrayOne[0] < arrayTwo[0]){
      sorted.push(arrayOne.shift());
    } else{
      sorted.push(arrayTwo.shift());
    }
  }
  return sorted.concat(arrayOne).concat(arrayTwo);
}

function mergeSort(array){
  let arrayLength = array.length;
  let midpoint = arrayLength/2;
  let firstHalf = array.slice(0, midpoint);
  let secondHalf = array.slice(midpoint, arrayLength);
  if(arrayLength < 2){
    return array;
  } else{
    return merge(mergeSort(firstHalf), mergeSort(secondHalf));
    // ^ *** only required change made here ***
  }
}

Note: There are several other optimization that can be made but the above is the minimal change to your code required to address the bug. If you're doing this as a learning exercise, I would suggest looking at some other implementations when you are finished.

Collectives™ on Stack Overflow

Recursive merge sort function error: Cannot read property 'length' of undefined

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related