 <p>It totally depends on your version of distributed insertion sort. One solution can be as follows:</p> <ol> <li>Array A (with n elements) is shared to all nodes in the system. </li> <li>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.)</li> <li>Now, each node can sort its slice using insertion sort. </li> <li>The sorted sub-arrays in each node can be merged either through merge sort of insertion sort. </li> </ol> <p>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. </p>