https://i.imgur.com/XJwuUoF.jpg
请问这题怎么算？有爬过文但还是不太懂。
第一小题我的想法是分成两步骤：
1.quick sort:
因为每条有k个元素，所以worst case是k^2,然后做n/k次 =》总共k^2 * (n/k)
2. merge:
共有n/k条，每回合两两比较，最多比较k次，要merge log(n/k)回合=》总共 k*log(n/k)
请问这样的想法哪里有错吗？
还有借问一下有人有比较完整的资结解答吗？手写题的解答真的好难找qq
或是有人有写题的群可以让小弟我加的吗，谢谢。
作者: cossetannie (paa) 2019-12-11 12:17:00
merge最多是比较n个
我发现我有地方好像想错 每条k个元素 这样两条拿来merge最多比2k-1次 然后每回合都是两两merge 总共要log(n/k) 回合 但感觉这样答案还是不对
作者: a9778875 (Mine) 2019-12-11 14:44:00
所以是两两比对时因为每条k个最多2k次 总共n/k条 两两比对的话要n/2k 组 每组又是2k次 相乘就是n 不知道我这样理解有没有错？
作者: cossetannie (paa) 2019-12-11 16:34:00
用整条是n个去想比较直接一点
我觉得这里的merge用selection tree的k-way merge去想比较好想selection tree共要做O(n)回合（因为要output n个data) 每回合需花log(n/k)次比较（树高）