Recursive merge sort with a generator function does not work as expected

Question

I am trying to observe my recursive merge sort slicing the arrays by each step.

function mergeSort(arr) {
  if(arr.length === 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArray = arr.slice(0, mid);
  const rightArray = arr.slice(mid, arr.length);

  console.log(leftArray, rightArray)

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

function merge(leftArray, rightArray) {
  const sortedArray = [];

  while(leftArray.length > 0 && rightArray.length > 0) {
    if(leftArray[0] < rightArray[0]) {
      sortedArray.push(leftArray[0]);
      leftArray.shift();
    } else {
      sortedArray.push(rightArray[0]);
      rightArray.shift();
    }
  }

  return sortedArray.concat(leftArray).concat(rightArray);
}

If you see the code above, I am logging leftArray and rightArray. But that logs every step at once as soon as I run the code. In order to control the code execution, I made my mergeSort function into a generator function so that whenever I run .next() I could see the next slice.

function * mergeSort(arr) {
  if(arr.length === 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArray = arr.slice(0, mid);
  const rightArray = arr.slice(mid, arr.length);

  yield console.log(leftArray, rightArray);

  return merge(mergeSort(leftArray), mergeSort(rightArray));
}

function merge(leftArray, rightArray) {
  const sortedArray = [];

  while(leftArray.length > 0 && rightArray.length > 0) {
    if(leftArray[0] < rightArray[0]) {
      sortedArray.push(leftArray[0]);
      leftArray.shift();
    } else {
      sortedArray.push(rightArray[0]);
      rightArray.shift();
    }
  }

  return sortedArray.concat(leftArray).concat(rightArray);
}

const list = [32, 12, 23, 52, 5, 16, 74, 21, 33, 55, 85];
const sort = mergeSort(list);

sort.next(); // I expected [32, 12], [23, 52, 5]
sort.next(); // [32, 12] and so on...

It turned out the result was not what I expected. I would very much appreciate it if you advise me on the usage of the generator function!

Answer 1

In merge sort, array is divided into smaller arrays till its size is 1. After this, it merge the smaller arrays such a way that the newly created array is also sorted.

To understand recursion you can trace all recursion levels with indentation. For example:

const log = (level, data) => {
    var s = ""
    for (i = 0; i < level; i++) {
        s += "    ";
    }
    console.log(s + data);
}

const merge = (left, right) => {
  const result = [];

  while(left.length && right.length){
    if(left[0] <= right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }

  while(left.length) result.push(left.shift());
  while(right.length) result.push(right.shift());
  return result;
}

const mergeSort = (array, level) => {
  log(level, "Start " + array);
  if(array.length < 2) {
    log(level, "Finish " + array);
    return array;
  }

  const middle = Math.floor(array.length / 2);
  log(level, "middle element " + array[middle])
  const leftArr = array.slice(0, middle);
  const rightArr = array.slice(middle, array.length);
  var result = merge(mergeSort(leftArr, level + 1), mergeSort(rightArr, level + 1));
  log(level, "Finish " + result);
  return result;
};

call the function with level value as 1.