归并排序

1. 归并排序

   归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
   作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
   1.自上而下的递归
   2.自下而上的迭归

2. 算法步骤

   申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
   设定两个指针，最初位置分别为两个已经排序序列的起始位置；
   比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
   重复步骤 3 直到某一指针达到序列尾；
   将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示
   

4. Js实现

   // 归并排序函数
   function mergeSort(arr) {
       // 边界条件，当数组长度为 1 时返回原数组
       if (arr.length === 1) {
           return arr;
       }
   
       // 将数组分成两个子数组
       const mid = Math.floor(arr.length / 2);
       const leftArr = arr.slice(0, mid);
       const rightArr = arr.slice(mid);
   
       // 递归排序子数组并将它们归并
       return merge(mergeSort(leftArr), mergeSort(rightArr));
   }
   
   // 归并函数，将两个有序数组合并为一个有序数组
   function merge(leftArr, rightArr) {
       const result = [];
   
       while (leftArr.length > 0 && rightArr.length > 0) {
           if (leftArr[0] <= rightArr[0]) {
               result.push(leftArr.shift());
           } else {
               result.push(rightArr.shift());
           }
       }
   
       // 将剩余的元素合并
       while (leftArr.length > 0) {
           result.push(leftArr.shift());
       }
       while (rightArr.length > 0) {
           result.push(rightArr.shift());
       }
   
       return result;
   }

5. Go实现

   func mergeSort(arr[]int)[]int {
       length:= len(arr)
       if length < 2 {
           return arr
       }
       middle:= length / 2
       left:= arr[0:middle]
       right:= arr[middle:]
       return merge(mergeSort(left), mergeSort(right))
   }
   
   func merge(left[]int, right[]int)[]int {
       var result []int
       for len(left) != 0 && len(right) != 0 {
           if left[0] <= right[0] {
               result = append(result, left[0])
               left = left[1:]
           } else {
               result = append(result, right[0])
               right = right[1:]
           }
       }
   
       for len(left) != 0 {
           result = append(result, left[0])
           left = left[1:]
       }
   
       for len(right) != 0 {
           result = append(result, right[0])
           right = right[1:]
       }
   
       return result
   }