Question $1$

MERGESort involves a step that merges two sorted lists in $O(n)$ time. Show that one can use a max heap to perform this merge on $k$ sorted lists in tilde$(O)(n)$ time or prove that it is impossible.

Note: tilde$(O)(n)$ is called soft$-O.$ A function $f(n)$ is tilde$(O)(g(n))$ if $f(n)inO(g(n)lo{g}^k(n))$ for some $k.$ That is$,$

$f(n)$ is $O(g(n))$ after ignoring $log$ factors.