$(30$ points$)$ Question $2$

In class, we talked about the linear time complexity O$($n$),$ and we gave an example of merging

two sorted lists into a single sorted list.

Now, let's elevate the complexity a bit. Imagine you have k sorted lists with n elements in total.

Your task is to merge these k sorted lists into one single sorted list efficiently.

Here's the challenge: Your algorithm should accomplish this in O$()$ time complexity. I'll

offer a hint: use a heap for k$-$way merging.