You have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.