合并排序和选择排序

Question

我在为一个算法开发递归时遇到了麻烦，该算法对大于m的列表大小使用递归合并排序调用。它对小于或等于m的列表大小使用选择排序。

下面是我的伪代码：

proc merge_and_selection (A, p, r, m) {
if (p <= r) then
   q = (p + r)/2
   
   if r - p > m then
      merge_and_selection(A, p, q - 1, m)
      merge_and_selection(A, q + 1, r, m)
   else
      selection_sort(A, p, q - 1)
      selection_sort(A, q + 1, r)
   end

   merge(A, p, q, r)
end if 
}

我认为重现是：

​

​

其中T(2) = m(m-1)/2

Answer 1

我认为更准确的公式如下：

• T(n) = 2*T(n/2) + Theta(n)，n >= m/2
• T(n) = Theta(n^2)，n< m/2