Parallel algorithm to check if a sequence is sorted

Question

I need a parallel algorithm (cost optimal) to check if a given sequence of n numbers is sorted .

Answer 1

For m threads, give each thread a chunk of n/m consecutive numbers with an overlap of 1 number. In each thread, check that that the sequence it is assigned is in sorted order. If all subsequences are sorted, then the entire sequence is sorted.

Examples:

[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

* this is the overlap of 1.

This solution has complexity O(n/m).