概述

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为nlognO.svg（大O符号）。
1945年由约翰·冯·诺伊曼首次提出。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

算法步骤

  1. 分割：递归地把当前序列一分为二。
  2. 递归：子序列递归排序
  3. 集成：合并有序子序列

    排序过程

    Merge-sort-example-300px.gif

    复杂度

    | 平均时间复杂度 | nlogn.svg | | —- | —- | | 最坏时间复杂度 | nlogn.svg | | 最优时间复杂度 | nlogn.svg | | 空间复杂度 | Θ(n) | | 最佳解 | 有时是 |