View Single Post
Mar8-12, 09:12 PM
HW Helper
P: 7,133
Quote Quote by rcgldr View Post
OK, but in one type of optimized case, there are k n copies done and in the worst case, (k) (k-1) n = (k2 - k) n compares done, how do you balance the copies versus compares for O(...) in this case?
Quote Quote by Max.Planck View Post
How did you get these numbers?
By merging k lists at the same time (one type of optimized case), k n elements copied, k-1 compares (worst case) for each element copied. This would be one of the "less expensive" implementations mentioned at the end of the original post.