Это полностью зависит от вашей версии распределенной вставки. Одно из решений может быть следующим:
- Массив A (с n элементами) используется всеми узлами системы.
- Массив A можно разбить на подмассивы A1, A2, A3, ..., Ap, где p - количество машин в системе. Это разбиение выполняется распределенным. То есть каждый узел находит нижнюю границу и верхнюю границу своего подмассива. (это можно сделать, найдя медианы, разделив массив и снова найдя медиану и т. д.)
- Теперь каждый узел может сортировать свой фрагмент, используя сортировку вставкой.
- Сортированные подмассивы в каждом узле могут быть объединены с помощью сортировки слиянием сортировки вставкой.
Примечание. Неправильно измерять эффективность распределенного алгоритма путем подсчета количества обновлений. Поскольку многие обновления выполняются одновременно, следует учитывать общую сложность времени выполнения.