Параллельный алгоритм, чтобы проверить, отсортирована ли последовательность

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 (н / м).