Bitonic sort

近期正在学习Udacity平台推出的《Introduction to parallel programming》课程，在该课程中提及了一种颇具趣味性的并行算法——Bitonic sort（双调排序）算法。在学习过程中，我一直未能理解为何Bitonic sort算法能够确保排序的准确性，因此花费了数日时间查阅相关资料。期望本文能够为同样存在疑问的读者带来一定的启发~

Bitonic sequence

要理解Bitonic sort算法，首先需要掌握Bitonic sequence（双调序列）的概念。
若有一个序列A=[x0, x1, x2, …, xn-1]，存在某个下标i（0≤i≤n-1），满足以下条件：

x0≤x1≤…≤xi，同时xi≥xi+1≥…≥xn-1

则该序列被称为Bitonic序列。
需要特别注意的是：
1. 若一个序列是严格递增或严格递减的（更准确地说应为非递减或非递增，但为了便于理解，在本文中将非递减等同于升序，非递增等同于降序），它同样属于Bitonic序列。
2. Bitonic序列的任意子序列依然是Bitonic的。
3. 对一个Bitonic序列执行循环移位操作后，其结果仍然是一个Bitonic序列（例如原序列为(d, a, b, c)，向右循环移位一次后得到(c, d, a, b)）。
因此