设待排序的元素数目为n，以n为偶数来说明奇偶置换排序。奇偶置换排序用n个阶段完成对n个元素的排序，每一个阶段需要n/2个比较+交换操作。这n个阶段分成两类，分别称为奇操作阶段和偶操作阶段。设是待排序的序列，在每个奇操作阶段，奇数索引的元素与自己的右邻居进行比较并在必要时交换，即。同样，在每个偶操作阶段，偶数索引的元素与自己的右邻居进行比较和交换，即。经过n个阶段进行这样的操作后，整个序列便处于排序状态。因为每个阶段需要次比较，而一共n个阶段，所以算法的时间复杂度为。奇偶置换冒泡排序的串行程序见图6.2.4，图6.2.5是一个简单的示例。