合并-插入排序开始插入排序的最佳元素数是多少？ [英] What is the optimum number of elements for a merge-insertion sort to begin insertion sort?

问题描述

我目前正在学习算法，并遇到了这种混合合并-插入排序算法。如果给出合并-插入排序算法，如

mergesort(arr, start, end)
  if (end - start <= X)
    perform insertionsort
  else if (end - start > X)
    mergesort(arr, start, mid)
    mergesort(arr, mid+1, end)
    merge(arr, start, end)

如何找到此混合算法优于普通合并排序算法的最佳X级别？

推荐答案

X的最佳数值通常在16到96之间。Visual Studio使用32。对于伪随机数据，它没有那么大的帮助，对于大型数组，排序时间只减少了大约10%。

这篇关于合并-插入排序开始插入排序的最佳元素数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！