1. 将元素对半分割，递归分割子元素，直到剩下一个子元素
2. 递归合并分割的子元素，合并成有序数组

3. 时间复杂度 O(logn)，空间复杂度 O(logn)

   代码

   ```javascript function mergeSort(arr) { if (arr.length < 2) { return arr; }

   const middle = Math.ceil(arr.length / 2); const left = arr.slice(0, middle); const right = arr.slice(middle);

   return merge(mergeSort(left), mergeSort(right)); }

function 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;
} ```