修改合并排序以使用插入排序Java实现合并排序 [英] Modification to merge sort to implement merge sort with insertion sort Java

问题描述

我想实施修改以合并 sort，其中使用插入排序对长度为k的n/k个子列表进行排序，然后使用 合并排序的标准合并机制. 我想知道对于朗姆酒时间复杂度而言，合并排序的修改版本等于合并排序的原始版本的值k必须等于什么.这是我自己的概念性练习.代码和/或解释表示赞赏.

I want to implement a modification to merge sort, where n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism of merg sort. I'm wondering what the value k has to equal for the modified version of merge sort to equal the original version of merge sort in terms of rum time complexity. This is a conceptual exercise by myself for myself. Code and or an explanation is appreciated.

推荐答案

您的n/k路合并为O(n ^ 2/k)(说明

Your n/k-way merge is O(n^2/k) (explanation here). Each of your individual insertion sorts are O(k^2). Observe that for any value of k, your overall running complexity will remain O(n^2); therefore, no value of k will allow your modified merge sort to be O(nlogn)

这篇关于修改合并排序以使用插入排序Java实现合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！