Запутался, как работает эта двойная рекурсия

Question

Мне была задана проблема сортировать массив с помощью сортировки слиянием . Я следую за курсом, и я не понимаю, как работает их решение. Я понимаю большую часть этого, но двойная рекурсия - это то, чего я не понимаю. Я создавал консольные журналы, и я не могу понять, как я получаю эти распечатанные результаты. Любая помощь будет высоко ценится.

Вот код:

var mergeSort = function (nums) {
  if (nums.length <= 1) return nums;

  let mid = Math.floor(nums.length / 2);
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);

  left = mergeSort(left); //RECURSION
  right = mergeSort(right); //I'M CONFUSED HOW THIS SECOND RECURSIVE CALL WORKS
  console.log("left", left);

  let block = [];
  let l = 0;
  let r = 0;

  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
      block.push(left[l]);
      l++;
    } else {
      block.push(right[r]);
      r++;
    }
  }

  if (l < left.length) {
    block = block.concat(left.slice(l));
  } else if (r < right.length) {
    block = block.concat(right.slice(r));
  }
  return block;
};
console.log("result", mergeSort([3, 4, 2, 1]));   //TEST CASE

Answer 1

Интересно, поможет ли это:

Если мы добавим некоторые записи в вашу функцию, мы можем сгенерировать такой вывод:

mergeSort ([3,4,2,1])
  left:
    mergeSort ([3,4])
      left:
        mergeSort ([3])
        ==> [3]
      right:
        mergeSort ([4])
        ==> [4]
      merge ([3], [4])
    ==> [3,4]
  right:
    mergeSort ([2,1])
      left:
        mergeSort ([2])
        ==> [2]
      right:
        mergeSort ([1])
        ==> [1]
      merge ([2], [1])
    ==> [1,2]
  merge ([3,4], [1,2])
==> [1,2,3,4]

result: [1,2,3,4]

Рекурсивный вызов ничего не завершает. Он просто возвращает значение тому, кто его вызвал. В root это начальный вызов mergeSort. Для внутренних вызовов это вызов для сортировки левой половины или сортировки правой половины.

Таким образом, при каждом вызове mergeSort, когда мы не достигаем нашего базового случая, мы разбиваем Оставшийся массив пополам (-i sh) и рекурсивно вызвать его для сортировки левой половины, затем рекурсивно вызвать его для сортировки правой половины, а затем объединить две половины обратно, что просто, поскольку теперь они отсортированы.

Это одна из тех вещей, которые вы можете обнаружить, играя в карты. Если вы хотите отсортировать всю колоду со случайным перемешиванием, один из лучших способов - разделить ее пополам, отсортировать каждую половину и объединить их, поместив перед собой две отсортированные стопки, постоянно вытягивая наименьшее значение из тех, которые отображаются в добавить в свою основную кучу. Но для сортировки одной из этих полукодок лучше всего разделить ее пополам, отсортировать ... И, таким образом, рекурсию. Я лично сделаю это на несколько уровней. Когда я получаю три или четыре карточки, я сортирую их по проверке.

Этот фрагмент показывает, как я добавил запись:

const log = (indent, message) => 
  console.log (Array(indent * 2).fill(' ').join('') + message)


var mergeSort = function (nums, indent = 0) {
  log (indent, `mergeSort ([${nums}])`)
  if (nums.length <= 1) {
    log (indent, `==> [${nums}]`)
    return nums;
  }
  
  let mid = Math.floor(nums.length / 2);
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);

  log (indent + 1, 'left:')
  left = mergeSort(left, indent + 2); 
  log (indent + 1, 'right:')
  right = mergeSort(right, indent + 2); 

  let block = [];
  let l = 0;
  let r = 0;

  log (indent + 1, `merge ([${left}], [${right}])`)
  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
      block.push(left[l]);
      l++;
    } else {
      block.push(right[r]);
      r++;
    }
  }

  if (l < left.length) {
    block = block.concat(left.slice(l));
  } else if (r < right.length) {
    block = block.concat(right.slice(r));
  }
  log (indent, `==> [${block}]`)
  return block;
};

console .log ('', `result: [${mergeSort([3, 4, 2, 1])}]`)

Answer 2

Я думаю, что эта версия может помочь вам увидеть, как выполняются вызовы:

var mergeSort = function (nums, stackNumber, calledFromSide) {
  if (nums.length <= 1) return nums;

  let mid = Math.floor(nums.length / 2);
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);
  console.log(`stackNumber: ${stackNumber}, calledFromSide: ${calledFromSide}, left:${left}, right:${right}`);
  left = mergeSort(left, stackNumber + 1, 'left'); //RECURSION
  right = mergeSort(right, stackNumber + 1, 'right'); //I'M CONFUSED HOW THIS SECOND RECURSIVE CALL WORKS


  let block = [];
  let l = 0;
  let r = 0;

  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
      block.push(left[l]);
      l++;
    } else {
      block.push(right[r]);
      r++;
    }
  }

  if (l < left.length) {
    block = block.concat(left.slice(l));
  } else if (r < right.length) {
    block = block.concat(right.slice(r));
  }
  return block;
};
console.log("result", mergeSort([3, 4, 2, 1], 1, 'root'));   //TEST CASE