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...


??