归并排序算法在多核CPU中应用的分析

[boji123]

• 排序算法，大家应该都很熟悉了，常见的排序算法有：

  • 冒泡排序
  • 桶排序（计数排序）
  • 归并排序（合并排序）
  • 快速排序
  • 堆排序

• 在这么多算法中，我认为归并排序是最优雅的，首先，它拥有一个十分简洁的表达形式而且几乎在任何情况都适用，下面来看一下对比与分析：

• 归并排序算法的步骤：

  • 1、把数列对半一分为二，记为A、B
  • 2、递归地对子列进行排序
  • 3、将排好序的子列合并为一个排好序的大列

• 从归并排序的步骤里可以看出，这是有递归、分治的思想在里面的，而这种思想非常适合多核运算：我可以很方便地把一个问题均分为四份然后当作四个独立的子任务交由四个CPU进行。

• 合并的过程是有序的（从前往后顺推），因此可以很方便的对巨大的表进行合并：可以每次只从硬盘读出一小部分数据到内存进行合并，这样可以避免过于集中的IO调用以及过重内存占用。

• 对比其他的合并方式：

  • 堆排序和归并排序复杂度相当，然而堆排序大量的指针访问会线性地影响运行时间，且相比归并排序更加消耗内存
  • 快速排序在适应系统数据特点的时候可以很快，但是其稳定性不足，任务难以平均分配给多核CPU，且实现复杂，
  • 桶排序过度占用内存，且使用限制大

• 总结一下，数据结构并不是越复杂越高端越好，很多时候，伟大的规律总是简洁而深刻