sorting - 分布式系统中的插入排序

Question

插入排序如何处理分布式系统中数组的多个副本？我问是因为读取数据比写入数据更容易。就更新次数而言，分布式系统中算法的成本是多少？

Answer 1

这完全取决于您的分布式插入排序版本。一种解决方案如下：

1. 阵列 A（具有 n 个元素）被系统中的所有节点共享。
2. 阵列 A 可以划分为子阵列 A1、A2、A3、...、Ap，其中 p 是系统中的机器数。这种划分是分布式执行的。也就是说，每个节点找到其子数组的下界和上界。（这可以通过找到中位数和拆分数组并再次找到中位数等来完成。）
3. 现在，每个节点都可以使用插入排序对其切片进行排序。
4. 每个节点中已排序的子数组可以通过合并排序或插入排序进行合并。

注意：通过计算更新次数来衡量分布式算法的有效性是不正确的。就同​​时执行许多更新而言，应考虑执行的总时间复杂度。