http://i.imgur.com/EpYMCaR.jpg
http://i.imgur.com/V780JSj.jpg
請問這題中 per level 的時間為什麼是 O（nlog2(k)）?! 到底怎麼來的

我的理解是這邊的selection tree是用在每一層的k-way merge上https://i.imgur.com/JgKv6TB.jpg如圖，在決策樹每一層中的目標是合併k個run變成1個run，利用selection tree，建tree時間可以不管。1.每次從k個run中決定最小值相當於selection tree的樹高2.因為k-way，一共有k*(n/m)個data要爬上root3.一共有m/k棵selection tree要做，所以把這些相乘就是O(nlog_2k)第二步驟就是計算決策樹的高度，這是總共merge的次數，算出來就是答案了 有錯還請指正>_<