# Merge K sorted Arrays (JavaScript using generators)

Question: Merge k sorted Arrays

My main concerns about my code are:

1. Performance: is it optimized and is my description of the time and complexity correct. How should I annotate the space and time complexity at every step of the code?

2. What effect do generators have on the time and space complexity?

3. Is my code self-documenting, modular, and readable and how can it be written better?

Solution:

1. convert the sorted arrays into a Set data structures O(N)

2. create a generator function which takes in the iterative values, converts them into the values type, while removing the first value as an argument to be passed to the resulting iterations.

3. I iterate over the remaining sets O(N)

4. I Use another generator function to merge the values O(N*N)-> O(N^2)

5. In the merge generator, I set three-pointers and iterate them over the combined lengths of the two target arrays, the accumulated array setA with the next sequential array setB. I then iterate the ri pointer over the space of both arrays

6. In the merge generator, I check if setA pointer is > than the length of all possible setA, this leaves setB at its current pointer as the only viable solution set. I yeld its value inside the generator space. I also default to the pointer at SetB if the value at SetA is larger than that at SetB. Otherwise, the value at SetA is at a higher priority and I yield setA's value to the solution space of the generator at ri.

7. in the merge generator space setA is the accumulation placeholder

8. as I yield the pass in the mergeSortedSets generator I have to lazy load the yielded values

because of that, I think the run-time complexity is at worst O(N^3) (I think this might be wrong)

function* mergeSortedSets(iterative, sets = iterative.values(), pass = sets.next().value) {
for (let set of sets) {
yield pass = [...merge(pass, set)]
}
}

function* merge(setA, setB) {
for (let ri = 0, ai = 0, bi = 0; ri < setA.length + setB.length; ri++) {
if (ai >= setA.length || setA[ai] > setB[bi]) yield setB[bi++];
else yield setA[ai++];
}
}

let reduce = mergeSortedSets(new Set([
[1, 4, 5],
[1, 3, 4],
[2, 6],
[2, 3, 4]
].map(iterative => iterative)))

for (let result of reduce) {
console.log(result)
}