/*
Merge A List Of Sorted Arrays
Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence. For example, if the input is [3, 5, 7], [0, 6], and [0, 6, 28], then the output is [0, 0, 3, 5, 6, 6, 7, 28].
3 pointers for the current element in the array, time cost O(N) and space cost O(N)
*/
public class MergeSortedArrays {
public int[] merge(int[] arr1, int[] arr2, int[] arr3) {
int i = 0;
int j = 0;
int k = 0;
int r = 0;
//[3, 5, 7], [0, 6], and [0, 6, 28] [0 0 3 5 6 6 7 28]
int[] result = new int[arr1.length + arr2.length + arr3.length];//8
while(i < arr1.length && j < arr2.length && k < arr3.length) {//2 2 1
int t = min(arr1, arr2, arr3, i, j, k); //2
if(t == 1) {
result[r++] = arr1[i++];
} else if(t == 2) {
result[r++] = arr2[j++];
} else {
result[r++] = arr3[k++];
}
}
if(i == arr1.length) {
while(j < arr2.length && k < arr3.length) {
if(arr2[j] <= arr3[k]) {
result[r++] = arr2[j++];
} else {
result[r++] = arr3[k++];
}
}
} else if(j == arr2.length) {
while(i < arr1.length && k < arr3.length) { //////3 x 2
if(arr1[i] <= arr3[k]) {
result[r++] = arr1[i++];
} else {
result[r++] = arr3[k++];
}
}
} else {
while(j < arr2.length && k < arr3.length) {
if(arr2[j] <= arr3[k]) {
result[r++] = arr2[j++];
} else {
result[r++] = arr3[k++];
}
}
}
//3 2 3
if(i < arr1.length) {
result[r++] = arr1[i++];
} else if(j < arr2.length) {
result[r++] = arr2[j++];
} else {
while(k < arr3.length) {
result[r++] = arr3[k++];
}
}
return result;
}
//[3, 5, 7], [0, 6], and [0, 6, 28] 2 1 1
private int min(int[] arr1, int[] arr2, int[] arr3, int i, int j, int k) {
if(arr1[i] <= arr2[j] && arr1[i] <= arr3[k]) return 1;
else if(arr2[j] <= arr1[i] && arr2[j] <= arr3[k]) return 2;
else return 3;
}
public static void main(String...args) {
int[] arr1 = {3, 5, 7};
int[] arr2 = {0, 6};
int[] arr3 = {0, 6, 28};
MergeSortedArrays msa = new MergeSortedArrays();
int[] result = msa.merge(arr1, arr2, arr3);
for(int i : result) {
System.out.print(i + " ");
}
System.out.println();
}
}
