Использование параллельной карманной сортировки для одновременного упорядочения нескольких массивов данных

Показано, что при параллельной карманной сортировке массива положительных (включая ноль) случайных равномерно распределенных целых чисел или чисел с фиксированной запятой (алгоритм 2) [1] создаются такие структуры данных, которые позволяют упорядочивать одновременно $k$ массивов по $N/k$ элементов в каждом быстрее, чем за $O(N\log_2(N/k)/k)$ шагов, где $N$ — общее число элементов во всех массивах, $k$ — число процессорных элементов (ПЭ). Алгоритм удобно использовать на параллельной ЭВМ с $k$ ПЭ для предварительного упорядочения $k$ подмассивов из $N/k$ элементов, которое требуется в большинстве алгоритмов сортировки массива из $N$ элементов.