I have a big sorted array of unique numbers. I do want to split it into n smaller disjoint sorted arrays with unique values. For example, I have an array [1, 2, 3, 4, 5, 6, 7, 8, 9] and the algorithm I am looking for gives one of the following results (n=3):

1. [1, 4, 7], [5, 6, 9], [2, 3, 8]

2. [3, 8, 9], [1, 5, 7], [2, 4, 6]

3. [3, 4, 7], [1, 5, 8], [2, 6, 9], etc

Why I need it: I have a very big array (about 1 billion values) and I need to distribute values randomly between nodes in a simulated network, which together compute some aggregated value. They work more efficiently if they have sorted values. Since I am testing this system I need to run the simulation many times with the different amount of nodes, network topology, etc. Obviously simply splitting the data into several consecutive chunks is not suitable here.

CodePudding user response：

You can shuffle the list, split into chunks and the sort the chunks. For example (solution in Python):

import random

n = 3
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]

random.shuffle(lst)

for i in range(0, len(lst), n):
    print(sorted(lst[i : i   n]))

Prints:

[1, 2, 8]
[3, 6, 9]
[4, 5, 7]

CodePudding user response：

Create n smaller arrays and an array of n indices. There is one index for each of the small arrays; they are all initialized to zero. Iterate over the large sorted array, at each step choosing one of the small arrays to put the value into. If the small array is already 'full' (its index is already equal to the length of the array), pick the next small array that is not yet full. Insert the value from the large array into the small array at the current value of its index, and then increment the index.

This will require a fast random number generator and perhaps a clever way of taking the completed subarrays out of the rotation, but it is linear in the large sorted array and requires no sorting.