Сеть обменной сортировки со слиянием Бэтчера

[gaki]

> Они позволяют создавать масштабируемые параллельные алгоритмы сортировки больших объемов данных.

Всегда думал, что сети сортировки нужны для немасштабируемой сортировки данных небольшого, фиксированного объёма… «Всегда» в смысле с тех пор, как узнал о их существовании примерно месяц назад, вот с тех пор думал. Как-то тема параллельности и масштабируемости, по-моему, не очень раскрыта. Вот на первой и третьей иллюстрациях, например, у вас голубыми линиями разграничены участки, где компараторы можно параллельно исполнять, или что?

[BellaLugoshi]

сеть обменной сортировки со слиянием Бэтчера для параллельной сортировки массива произвольного размера

Читая Кнута (давно) не смог разобраться с этим методом, особенно с методом выбора пар и запоминанием того с какой парой работа уже проведена (это если мы говорим про параллельность). Очевидной была рекурсия и как я понял у вас она и используется, но это резко сужает фактор "произвольности размера".

В вашей статье уже в Примере 1 картинка и последовательность операций ниже мною не может быть сопоставлена вместе.

В общем вопросы остались без ответа.