javascript объединение сортировки и рекурсии

Question

Я пытаюсь понять, как работает JavaScript функция сортировки слиянием. И я изо всех сил пытаюсь понять, как работает рекурсивная функция. Это код:

const mergeSort = array => {
  if(array.length < 2) {
    //function stop here
    return array
  }

  const middle = Math.floor(array.length / 2);
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  return merge(mergeSort(leftSide), mergeSort(rightSide))

};

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;
}
mergeSort([5,3,8,10,4,1])

После разбиения исходного массива с помощью функции mergeSort, первые два элемента, переданные в функцию слияния, - это 3 и 8. Затем слияние вызывается снова, но с другими значениями и при этом сохраняется предыдущий вход. Как это возможно - после того, как он вызывается один раз, он сохраняет значения ([3,8]) и добавляет к ним больше значений?

Видео на YouTube, из которого я взял код

Answer 1

Чтобы понять рекурсию, вы можете отслеживать все уровни рекурсии с отступом. Например:

const mergeSort = (array, level) => {
  logWithLevel(level, "Start sort array " + array);
  if(array.length < 2) {
    //function stop here
    logWithLevel(level, "Finish sort array " + array);
    return array;
  }

  const middle = Math.floor(array.length / 2);
  logWithLevel(level, "middle element is " + array[middle])
  const leftSide = array.slice(0, middle);
  const rightSide = array.slice(middle, array.length);
  var result = merge(mergeSort(leftSide, level + 1), mergeSort(rightSide, level + 1));
  logWithLevel(level, "Finish sort array " + result);
  return result;
};

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 logWithLevel = (level, data) => {
    var s = ""
    for (i = 0; i < level; i++) {
        s += "    ";
    }
    console.log(s + data);
}

И результат:

> mergeSort([5,3,8,10,4,1], 0)
    Start sort array 5,3,8,10,4,1
    middle element is 10
        Start sort array 5,3,8
        middle element is 3
            Start sort array 5
            Finish sort array 5
            Start sort array 3,8
            middle element is 8
                Start sort array 3
                Finish sort array 3
                Start sort array 8
                Finish sort array 8
            Finish sort array 3,8
        Finish sort array 3,5,8
        Start sort array 10,4,1
        middle element is 4
            Start sort array 10
            Finish sort array 10
            Start sort array 4,1
            middle element is 1
                Start sort array 4
                Finish sort array 4
                Start sort array 1
                Finish sort array 1
            Finish sort array 1,4
        Finish sort array 1,4,10
    Finish sort array 1,3,4,5,8,10

Answer 2

function mergeSort(input) {
  const {length:arraySize} = input;
  if (arraySize < 2) return input;
  const mid = Math.floor(arraySize/2);
  const sortedLeftArray = mergeSort(input.slice(0,mid));
  const sortedRightArray = mergeSort(input.slice(mid, arraySize));
  return merge(sortedLeftArray, sortedRightArray);
}

function merge (left, right){
  let result = []
  while(left.length && right.length){
    if(left[0]< right[0]){
      result.push(left.shift())
    }else{
      result.push(right.shift())
    }
  }
  /* Either left/right array will be empty or both */
  return [...result, ...left, ...right];
}

console.log(mergeSort([5,3,8,10,4,1]))