http://i.imgur.com/WdeKDSx.jpg
因为我写不出递回式，所以用iterative分析：
1 因为merge的过程中只要其中一个run为空就会马上return 所以不管是n/k跟n/k做merge
或是3n/k与n/k做merge应该都是花O(n/k)的时间
2 因为他是依序往后merge所以总共会执行k回合
这样分析下来应该是k*n/k也就是O(n)吧？
为什么答案是给n*k？话说题目说的following algorithm是...?(104交大资演)
如果每次merge都要做最大run原是个数的时间才有机会被bound在n*k吧？

最后一次做merge的时候会花O((k-1)*n/k)，感觉这时候不能说bound在O(n/k)但每次merge都被bound在O(n)是肯定的这样子想好了，第一次是O(n/k)，第二次是O(2*n/k)...把每一次加起来就是O(n/k)+O(2*n/k)+...+O((k-1)*n/k)=n/k*(1+2+3+...+k-1)=O((n/k)*k*(k-1)/2)=O(n*k)第二行忘记用big-O包起来了

应该是1的地方错了吧 假设k=10 n=2 会有2 2 2 2 2个data然后你做完第一轮后 是4 2 2 2, 4在跟2 merge所以你每一轮的merge跟k没关系 是跟n有关 他又说merge在linear time, 所以merge的time是n n作k回=O(nk)