multithreading - 检查序列是否排序的并行算法

Question

我需要一个并行算法(成本最优)来检查给定的 n 个数字序列是否已排序。

Answer 1

对于 m 个线程，给每个线程一个 n/m 个连续数字的 block ，其中有 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

* 这是 1 的重叠。

这个解决方案的复杂度为 O(n/m)。