prompter: 用JS编写归并排序函数

assistant: /**
 * 
 归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，
该算法采用经典的分治（divide-and-conquer）策略
（分治法将问题分(divide)成一些小的问题然后递归求解，
而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

 * 
 */

let arr = [8, 4, 5, 7, 1, 3, 6, 2, 0, 77];
let temp = new Array(arr.length);//归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
console.log(arr);

//分+合方法
function mergeSort(arr, left, right, temp) {
    if (left < right) {//中间索引
        let mid = Math.floor((left + right) / 2);
        //向左递归进行分解
        mergeSort(arr, left, mid, temp);
        //向右递归进行分解
        mergeSort(arr, mid + 1, right, temp);
        //到合并
        merge(arr, left, mid, right, temp);
    }

}

//合并的方法
/**
 * 
 * @param {排序的原始数组} arr 
 * @param {左边有序序列的初始索引} left 
 * @param {中间索引} mid 
 * @param {右边索引} right 
 * @param {做中转的数组} temp 
 */
function merge(arr, left, mid, right, temp) {
    let i = left;//初始化i，左边有序序列的初始索引
    let j = mid + 1;//初始化j，右边有序序列的初始索引
    let t = 0;//指向temp数组的当前索引

    //1、先把左右两边（有序）的数据按照规则填充到temp数组
    //直到左右两边有序序列，有一边处理完毕为止
    while (i <= mid && j <= right) {
        //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
        //即将左边的当前元素，拷贝到temp数组
        //然后t++,i++
        if (arr[i] <= arr[j]) {
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            //反之，将右边的有序序列的当前元素，填充到temp数组
            temp[t] = arr[j];
            t++;
            j++;
        }
    }
    //2、把有剩余数据的一边一次全部填充到temp
    while (i <= mid) {
        //左边的有序序列还有剩余的元素，就全部填充到temp
        temp[t] = arr[i];
        t++;
        i++;
    }
    while (j <= right) {
        //右边的有序序列还有剩余的元素，就全部填充到temp
        temp[t] = arr[j];
        t++;
        j++;
    }
    //3.将temp数组的元素拷贝到arr
    t = 0;
    let tempLeft = left;//
    while (tempLeft <= right) {
        //第一次合并tempLeft = 0,right=1
        //第二次合并 templeft = 2,rigth=3
        //最后一次合并 templeft = 0,right=7
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

assistant: 归并排序（MergeSort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。归并排序的算法时间复杂读为O(NLogN)，是一种稳定的排序算法。

```js
function mergeSort(array) {
  const half = array.length / 2
  
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

// 把两个排好序的子数组（left、right）合并来获得一个排好序的大数组
function merge(left, right) {
    let arr = []
    // 如果任何一个数组为空，就退出循环
    while (left.length && right.length) {
        // 从左右子数组的最小元素中选择较小的元素
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // 连接剩余的元素，防止没有把两个数组遍历完整
    return [ ...arr, ...left, ...right ]
}


```

assistant: 下面是归并排序函数：
```js
    function mergeSort(arr) {
      if (arr.length <= 1) {
        return arr;
      }

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

      const leftSorted = mergeSort(leftArr);
      const rightSorted = mergeSort(rightArr);

      return merge(leftSorted, rightSorted);
    }

    function merge(leftArr, rightArr) {
      let leftIndex = 0;
      let rightIndex = 0;
      const resultArr = [];

      while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if (leftArr[leftIndex] < rightArr[rightIndex]) {
          resultArr.push(leftArr[leftIndex]);
          leftIndex++;
        } else {
          resultArr.push(rightArr[rightIndex]);
          rightIndex++;
        }
      }

      return resultArr.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
    }
``` 
这个归并排序函数使用了递归来拆分输入数组，直到每个子数组的长度都小于等于 1。然后，它将两个排序后的子数组合并成一个排序后的数组，最后返回这个排序后的数组。

你可以将一个数组传递给 <code>mergeSort </code>函数
```js
    const arr = [4, 2, 7, 1, 3, 5, 6];
    const sortedArr = mergeSort(arr);
    console.log(sortedArr); // 输出 [1, 2, 3, 4, 5, 6, 7]
```