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])

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