2 questions

[tukilala]

needs to make sorted list with size n^2, from n sorted lists, each list with size n.

what is the complexity of the 2 next algorithm, and why?

1. every list have a pointer on the first element. and by compare each time all the elements, pick the smallest and insert him to the n^2 list, and promote the promote pointer.

2. merge every 2 lists, so in the first step there are n/2 merges, second step n/4 merges and so on...


??

[prime1999]

1. O(n^3) -- to pick the element to insert into the final list (n^2 times), you compare all the elements (n comparisons).
2. O(n^2 log n) -- No. of operations done for k (k>1) lists F(k) = 2 F(k/2) + c n k where c is a constant. This evaluates to F(k) = k n log k.

There is another way to speed up the first algorithm -- using a heap to retrieve the smallest (and not comparing them all over again).
See http://www.codeguru.com/forum/showpost.php?p=1856789#5