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)