バイトニックソートの比較操作で「出力が2つのバイトニック列になる」という説明が理解できません

Question

『実践Rust入門』という本を読んでいる中で、バイトニックソート(Bitonic sorter)についての説明がありました。アルゴリズム自体は理解できたのですが、その説明の中で納得できない箇所がありました。

「要素数nのバイトニック列の各要素をn/2個右の要素と比較して、指定されたソート順になるよう交換する」という操作を
[1, 3, 5, 6, 8, 7, 4, 2]
について実施すると、
[1, 3, 4, 2, 8, 7, 5, 6]
になるということについては問題なく理解できました。

ただ、

…この数列を前半と後半に2分割する

[1, 3, 4, 2] [8, 7, 5, 6]
すると、それぞれがバイトニック列になっていることが分かる

という説明に納得がいきません。

この数列の場合だと、たしかに2分割したそれぞれがバイトニック列になっていますが、以下のような例だと、2分割したあとのそれぞれの数列はバイトニック列にはならないのではないでしょうか？

例1
[1, 2, 3, 4, 8, 7, 6, 5]
↓
[1, 2, 3, 4, 8, 7, 6, 5]
↓
[1, 2, 3, 4] [8, 7, 6, 5]

例2
[5, 6, 7, 8, 4, 3, 2, 1]
↓
[4, 3, 2, 1, 5, 6, 7, 8]
↓
[4, 3, 2, 1] [5, 6, 7, 8]

Wikipediaでも同様の説明があり、この本の筆者自身の誤りというわけでもなさそうです。

比較の操作では、入力列の上半分が下半分と決められた同じ方向に比較される。 もし入力がバイトニック列であれば、出力は上半分と下半分がそれぞれバイトニック列になり、…

バイトニックソート 日本語版Wikipedia

If the inputs happen to form a bitonic sequence (a single nondecreasing sequence followed by a single nonincreasing one or vice versa), then the output will form two bitonic sequences.

Bitonic sorter 英語版Wikipedia

アルゴリズム全体の理解・実装には影響しなさそうですが、疑問が残ってもやもやしています。
どなたかうまく解説いただけないでしょうか？

Answer 1

単調増加 or 減少の数列もバイトニック列です。なので、あげている例の2つともバイトニック列二つに分割できています。

Comments

[mitzzz]

なるほど、理解できました。ありがとうございます。