並行算法檢查序列是否排序

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 

*這是1

該溶液的重疊具有複雜度O（N/M）。