BitonicSort双调排序

本文章参考如下两篇文章，感谢作者：

参考1：Rachel-Zhang's blog

参考2：batilei's blog

介绍

BitonicSort双调排序是一个非常适合并行化的排序算法。算法复杂度为O(n(logn)^2)，比快排O(nlogn)要慢，但是它的n在并行机（比如GPU）上可以并行化掉n，那么复杂度就变为O( (logn)^2 )了，自然比快排等要快。 （n并行机是在理想情况下的。对于数据量巨大的数据集，n是不会完全并行化掉的。）

Bitonic Sequence 双调序列

双调序列是一个先单调递增后单调递减 或者 先单调递减后单调递增的序列。

双调排序算法

若一个序列是双调序列，那么我们能用如下的方法获得排序序列：

将一个双调序列切成两半， 每一段的单调性统一， 然后如下图图1所示， 将两段叠放起来， 进行两两比较， 这样一定能够在左右两段分别得到一个双调序列（想想为什么得到的是两个双调序列）， 且左边的双调序列中元素全部小于右侧得到的双调序列的所有元素。 迭代这个过程， 每次都能将序列二分成两个子双调序列， 直到这个子双调序列的长度为2， 也就变成了一个单调子序列， 这个过程排序后原先的长双调序列就变为有序了 。 整个过程如下图所示。

任意序列生成双调序列

对于任意序列，如何用双调排序呢？

们可以将两个相邻的，单调性相反的单调序列看作一个双调序列， 每次将这两个相邻的，单调性相反的单调序列merge生成一个新的双调序列， 然后排序生成一个新的单调序列。 但要确保两个相邻的生成的新的单调序列单调性相反。这样，生成的新的相反序列又构成双调序列，能够进一步的合并，生成单调序列。最后，得到一个双调序列，生成一个单调序列。就结束了。看下图。