Parallel algorithm for checking sequence sorting

Question

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

Answer 1

For m threads, give each thread a piece of n / m consecutive numbers with 1 number overlapping. In each thread, verify that the sequence assigned to it 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 overlap 1.

This solution has complexity O (n / m).