Insertion sort in a distributed system

Question

How does insertion sort deal with multiple copies of an array in a distributed system? I ask because it is easier to read data than to write it. What will be the cost of the algorithm in a distributed system in terms of the number of updates?

Answer 1

It totally depends on your version of distributed insertion sort. One solution can be as follows:

1. Array A (with n elements) is shared to all nodes in the system.
2. Array A can be partitioned into sub-arrays A1 , A2, A3, ... , Ap, where p is the number of machines in the system. This partitioning is performed distributed. That is to say, each node finds the lower bound and the upper bound of its sub array. (this can be done by finding medians and the splitting the array and the finding the median again and so on.)
3. Now, each node can sort its slice using insertion sort.
4. The sorted sub-arrays in each node can be merged either through merge sort of insertion sort.

Note: It is not right to measure the effectiveness of a distributed algorithm by counting the number if updates. As far as many updates are performed concurrently, the total time complexity of execution should be taken into consideration.