シーケンスがソートされているかどうかを確認する並列アルゴリズム

Question

与えられたn個のシーケンスがソートされているかどうかを調べるには、並列アルゴリズム（コスト最適）が必要です。

Answer 1

m個のスレッドの場合、各スレッドにn/m個の連続番号のチャンクに1つの番号の重複を付けます。各スレッドで、割り当てられている順序がソート順であることを確認します。すべてのサブシーケンスがソートされている場合、シーケンス全体がソートされます。

例：

[1, 4, 5, 6, 11, 42] => [1, 4, 5, 6*] and [6, 11, 42] with 2 threads 
[1, 4, 5, 6, 11, 42] => [1, 4, 5*], [5, 6, 11*] and [11, 42] with 3 threads 

*これは、この解決策は複雑さO（N/M）を有する1

の重なりです。