trjhtr

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++) 



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)