归并排序算法及分析

归并排序Merge Sort

• 下面我们来看看分治策略在排序中的应用
• 归并排序是递归算法， 思路是将数据表持续分裂为两半， 对两半分别进行归并排序递归的基本结束条件是：
  • 数据表仅有1个数据项，自然是排好序的；
  • 缩小规模：将数据表分裂为相等的两半，规模减为原来的二分之一；
  • 调用自身：将两半分别调用自身排序，然后将分别排好序的两半进行归并，得到排好序的数据表