I have this method to merge 2 sorted arrays into one sorted array:

    public void merge(T[] a, int l1, int r1, T[] b, int l2, int r2, T[] c, int l3) {
        while (l1 < r1 && l2 < r2) {
            if (a[l1].compareTo(b[l2]) < 0) {
                c[l3  ] = a[l1  ];
            } else
                c[l3  ] = b[l2  ];
        }

        while (l1 < r1)
            c[l3  ] = a[l1  ];
        while (l2 < r2)
            c[l3  ] = b[l2  ];
    }

But now I want to do it with 4 arrays at once.

I tried really long to come up with a solution, but wasn’t really successful. Does somebody have an idea how to do it?

CodePudding user response：

There is a much simpler way using Java8 streams than doing this by hand:

1. combine all arrays into one stream (i've used 2 but you can use as many as you want to):

int[] arr1 = {1, 7, 10};
int[] arr2 = {2, 1, 9, 4};

Stream<int[]> ints = Stream.of(arr1, arr2);

2. then flatMap and sort them in a stream:

IntStream intStream = ints.flatMapToInt(Arrays::stream).sorted();

and when you print them you will see all the numbers sorted:

intStream.forEach(System.out::println);

1
1
2
4
7
9
10

combined in a function, it could look something like this:

public int[] merge(int[]... arrays) {
  return Stream.of(arrays)
                 .flatMapToInt(Arrays::stream)
                 .sorted()
                 .toArray();
}

EDIT: The advantage of streams is, that you can further modify the values as you like. e.g. by leveraging the distinct function you can easily remove duplicates:

intStream = intStream.distinct();
intStream.forEach(System.out::println);

1
2
4
7
9
10

CodePudding user response：

Below is the description of how to merge an arbitrary number of sorted arrays:

• eliminate empty arrays;
• find the total number of elements and create a resulting array based on it;
• define an array that will maintain a current position in each of the source arrays;
• using a nested for loop for each position in the resulting array pick the lowest value of all currently accessible values.

The implementation might look like this:

public static int[] mergeNSorted(int[]... arrays) {
    int[][] normalized = getNormalized(arrays);
    
    int[] result = new int[getTotalLength(normalized)];
    int[] positions = new int[normalized.length]; // position for each array
    
    for (int pos = 0; pos < result.length; pos  ) {
        int minCurVal = Integer.MAX_VALUE;
        int curArr = 0;
        for (int i = 0; i < normalized.length; i  ) {
            if (positions[i] < normalized[i].length && normalized[i][positions[i]] < minCurVal) {
                minCurVal = normalized[i][positions[i]];
                curArr = i;
            }
        }
        result[pos] = minCurVal;
        positions[curArr]  ;
    }
    return result;
}

public static int[][] getNormalized(int[]... arrays) {
    return Arrays.stream(arrays)
        .filter(arr -> arr.length != 0)
        .toArray(int[][]::new);
}

public static int getTotalLength(int[]... arrays) {
    long totalLen = 0;
    for (int[] arr : arrays) totalLen  = arr.length;
    
    if (totalLen > Integer.MAX_VALUE) throw new IllegalArgumentException("total length exceeded Integer.MAX_VALUE");
    return (int) totalLen;
}

main() - demo

public static void main(String[] args) {
    int[][] input =
        {{1, 3}, {}, {2, 6, 7}, {10}, {4, 5, 8, 9}};

    System.out.println(Arrays.toString(mergeNSorted(input)));
}

Output

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