# 归并排序

# 算法原理

归并排序是一种分治算法。其基本思想是将待排序序列分成若干个子序列，对每个子序列进行排序，然后再将已排序的子序列合并成一个有序序列。归并排序采用递归的方式，将大问题分解为小问题，然后逐步解决。

# 算法步骤

将长度为n的输入序列分成两个长度为n/2的子序列
对这两个子序列分别采用归并排序
将两个排序好的子序列合并成一个最终的排序序列

# 动图演示

比较次数: 0

交换次数: 0

# 代码实现

function mergeSort(arr) {
  const len = arr.length;
  if (len <= 1) return arr;
  
  // 分割数组
  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 递归排序
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  
  // 比较左右数组的元素，将较小的元素放入结果数组
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  
  // 将剩余元素添加到结果数组
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

# 复杂度分析

# 时间复杂度

最好情况：O(n log n)
最坏情况：O(n log n)
平均情况：O(n log n)

# 空间复杂度

O(n)，需要额外的数组空间来存储合并结果

# 算法特点

# 优点

稳定排序
时间复杂度稳定，不受输入数据的影响
适合处理大规模数据
可以轻松实现并行化

# 缺点

需要额外的空间开销
对于小规模数据，可能不如插入排序等简单排序算法
递归调用会带来一定的函数调用开销

# 适用场景

大规模数据排序
要求稳定排序的场景
外部排序（当数据量太大，无法一次性载入内存时）
并行计算环境

# 优化方案

小规模数据使用插入排序：当子数组长度小于某个阈值时，使用插入排序
原地归并：减少空间开销
并行化处理：利用多线程进行子数组的排序

function optimizedMergeSort(arr) {
  const INSERTION_SORT_THRESHOLD = 10;
  
  function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
      const current = arr[i];
      let j = i - 1;
      
      while (j >= left && arr[j] > current) {
        arr[j + 1] = arr[j];
        j--;
      }
      
      arr[j + 1] = current;
    }
    return arr;
  }
  
  function sort(arr, temp, left, right) {
    // 小规模数据使用插入排序
    if (right - left <= INSERTION_SORT_THRESHOLD) {
      return insertionSort(arr, left, right);
    }
    
    const mid = Math.floor((left + right) / 2);
    
    // 递归排序
    sort(arr, temp, left, mid);
    sort(arr, temp, mid + 1, right);
    
    // 如果已经有序，则不需要合并
    if (arr[mid] <= arr[mid + 1]) {
      return arr;
    }
    
    // 合并两个有序数组
    merge(arr, temp, left, mid, right);
    
    return arr;
  }
  
  function merge(arr, temp, left, mid, right) {
    // 复制到临时数组
    for (let i = left; i <= right; i++) {
      temp[i] = arr[i];
    }
    
    let i = left;
    let j = mid + 1;
    let k = left;
    
    // 合并两个有序数组
    while (i <= mid && j <= right) {
      if (temp[i] <= temp[j]) {
        arr[k++] = temp[i++];
      } else {
        arr[k++] = temp[j++];
      }
    }
    
    // 复制剩余元素
    while (i <= mid) {
      arr[k++] = temp[i++];
    }
  }
  
  const temp = new Array(arr.length);
  return sort(arr, temp, 0, arr.length - 1);
}

← 插入排序快速排序 →