修改合并排序以使用插入排序Java实现合并排序

本文介绍了修改合并排序以使用插入排序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)(说明此处).您的每种插入类型均为O(k ^ 2).观察到，对于任何k值，您的总体运行复杂度将保持O(n ^ 2);因此，k的任何值都不允许修改后的合并排序为O(nlogn)

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)