算法导论8 Problems 答案

8-1

a

由于数组$A$将会有$n!$个不同的输入，这些输入都会以等概率的形式出现，而且这些原始输入都是决策树$T_A$的叶节点。因此$T_A$中每个叶节点都有$\dfrac{1}{n!}$的概率被原始输入命中，而其它内部节点由于不是来自原始输入，因此它们不会被原始输入命中，概率值为$0$。

b

当一棵树$LT$和另外一颗树$RT$与一个祖先节点共同构成一棵树$T$后，$LT,RT$中所有节点的深度都增加了$1$（当然也包括了叶节点）。由于祖先节点必定不是$T$的叶节点，因此$T$的叶节点必定来自于$LT,RT$中的叶节点，并且两棵子树的叶节点总数为$k$。由于所有非祖先节点都增加了$1$，那么按照$D$的定义，在$D(LT),D(RT)$的基础上，$D(T)$中所有的叶节点的深度都要增加$1$。因此$D(T)=D(LT)+D(RT)+k$。

c

如果树$T$的叶子节点的总数为$k$，那么必有$i$个节点来自左子树$T{L}$，$k-i$个节点来自右子树$T{R}$。如果$D(T)$需要最小化，那么各自独立的$D(T_L),D(T_R)$也需要最小化，根据$d,D$的定义，有：

$\begin{aligned}
d(k)&=\min {T \text{ have } k \text{ leaves}} {D(T)}\
&=\min{T \text{ have } k \text{ leaves}} {D(T{L}) + D(T{R}) + k}\
&=\min{i=1}^{k-1} {\min{LT \text{ have } i \text{ leaves}} {D(LT)} + \min{T \text{ have } k-i \text{ leaves}} {D(RT)} +k}\
&=\min{i=1}^{k-1} {d(i)+d(k-i) +k}\
\end{aligned}$

d

令$f(i)=i\lg i+(k-i)\lg(k-i)$，那么$f’(i)=\lg i-\lg(k-i),f’’(i)=\dfrac{1}{i\cdot \ln 2}+\dfrac{1}{(k-i)\cdot \ln 2}$。

当$f’(i)=0$时，得到$i=\dfrac{k}{2}$，此时得到$f’’\left(\dfrac{k}{2}\right)=\dfrac{1}{k\cdot \ln 2}>0$，也就是说$f(i)$在$i=\dfrac{k}{2}$处取到最小值$f\left(\dfrac{k}{2}\right)=k\lg k-k$。

假设$d(k_0)\ge ck_0\lg k_0$，对于$k_0< k$都成立，那么有

$\begin{aligned}
d(k)&=\min{i=1}^{k-1} {d(i)+d(k-i) +k}\
&\ge \min{i=1}^{k-1} {ci\lg i+c(n-i)\lg (n-i) +k}\
&= c\cdot \min_{i=1}^{k-1} {i\lg i+(n-i)\lg (n-i) } + k\
&= c(k\lg k-k)+k\
&= ck\lg k+(1-c)k\
&\ge ck\lg k&\qquad(A)
\end{aligned}$

其中，步骤$(A)$假设了$c\le 1$。

那么最终令$c=\min{1,d(2)/2}$。由数学归纳法，$d(k)=\Omega(k\lg k)$成立。

e

由于决策树$T_A$一共有$n!$个叶节点，因此$D(T_A)\ge d(n!)=\Omega(n!\lg(n!))$，即$D(T_A)= \Omega(n!\lg(n!))$.

那么平均时间复杂度满足$T(n)$满足$T(n)=\dfrac{D(T_A)}{n!}=\Omega(\lg (n!))=\Omega(n\lg n)$。

f

以上证明说明了确定性算法$A$中，每一个决策都是最优的。如果算法$B$采用随机决策，那么算法$B$可能会选到不是最优的决策，从而导致算法$B$的平均时间复杂度比$A$高。在这时，原本的算法$A$就比算法$B$优秀。

8-2

a

直接使用计数排序，其中参数$k=1$，时间复杂度为$\Theta(n+1)=\Theta(n)$。

b

直接使用快速排序，严格来说只需要调用一次算法PARTITION就可以完成。

SORT-0-1(A, n)
  for i = 1 to n
    if A[i] == 0
      exchange A[i] and A[n]
      PARTITION(A, 1, n)
      break
  

c

直接使用插入排序，不过算法的时间复杂度为$\Theta(n^2)$。

d

可以使用算法(a)解决，因为它同时满足了稳定性和时间复杂度的要求，直接以键的形式调用即可。

算法(b)不能的原因是不保证稳定性，算法(c)不能的原因是时间复杂度不满足要求。

e

如下算法做到了原地交换排序，并且是$O(n+k)$的时间复杂度，但是不是稳定的，第13行的while循环每执行一次那么总会有一个数到达了正确的位置。

COUNT-SORT'''(A, n, k)
  let B[0 : k], C[0 : k] and D[0 : k] be new arrays
  for i = 0 to k
    C[i] = 0
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1
  // C[i] now contains the number of elements equal to i.
  for i = 1 to k
    C[i] = C[i] + C[i – 1]
    B[i] = C[i - 1] + 1
    D[i] = C[i]
  // C [i] now contains the number of elements less than or equal to i.
  // B是每一段的起点，C是每一段的终点，当B[i] > C[i]说明这一段所有数已经复位。
  for i = 1 to n
    while B[A[i]] <= C[A[i]] and (i <= C[A[i]] or i > D[A[i]])
      k = A[i]
      exchange A[i] and A[C[k]]
      C[k] = C[k] - 1

8-3

a

先将每个数中按照数位个数放入每个桶中，然后每个桶内部使用基数排序即可（注意这里的基数排序算法RADIX-SORT'相比普通的基数排序算法RADIX-SORT，多了一个判断数组$A$是否为空的操作，如果为空那么立即返回。如果盲目运行RADIX-SORT，那么时间复杂度将会达到$\Theta(n^2)$）。

// m是数组长度。假设每个数x都有属性digits表示位数个数。
BUCKET-SORT`(A, m, n)
  let B[1 : n] be a new array
  for i = 1 to n
    make B[i] an empty list
  for i = 1 to m
    insert A[i] into list B[A[i].digits]
  for i = 1 to n
    RADIX-SORT'(B[i], B[i].size, i)
  concatenate the lists B[1], B[2], ... , B[n] together in order
  return the concatenated lists

最终，算法的时间复杂度为$\displaystyle{O\left(\sum_{i=1}^n i\cdot c_i\right)=O(n)}$，其中$c_i$表示数位为$i$的数的个数。

b

本算法使用的是自顶向下的桶排序算法，先考虑第一个字母，按照字母将它们分到不同的桶中，然后再递归处理每一个桶。将每个桶的字符串排好序后，再将这些字符串数组拼接在一起，从而保证了字典序。

由于每个字符串的每个字符都只会被访问一次，因此排序的时间复杂度为$O(n)$。

BUCKET-SORT`(S, pos)
  if S.size == 0
    return
  let B['a' : 'z'] be a new array
  let B0 be a new empty list
  for i = 'a' to 'z'
    make B[i] an empty list
  for i = 1 to S.size
    if pos <= S[i].size
      insert S[i] into list B[S[i, pos]]
    else
      insert S[i] into list B0
  for i = 'a' to 'z'
    BUCKET-SORT'(B[i], pos + 1)
  concatenate the lists B0, B['a'], B['b'], ... , B['z'] together in order
  return the concatenated lists

8-4

a

对于每一个红色水瓶，遍历每个蓝色水瓶进行倒水实验。如果发现一样多，那么相当于是匹配的，将这两个瓶子挪开并放到一边，拿下一个红色水瓶进行同样的尝试；如果尝试到只剩下一个，那么就不用尝试了。这个算法需要的次数最坏达到$\dbinom{n}{2}=\dfrac{n(n-1)}{2}=\Theta(n^2)$次。

b

将红色水壶先随机摆放成一个排列$r$，那么此时的问题就变成了确定一个排列$b$，使得$\forall 1\le i\le n,r_i=b_i$都成立。潜在的序列$b$的输入一共有$n!$个。而每一次比较，都会产生小于、等于和大于三种结果。因此假设这棵决策树是一个三叉树，其叶节点表示原始输入，内部节点表示比较的决策过程，那么其高度$h$满足$3^h\ge l\ge n!$，因此$h\ge n \log_3 n$。因此对于原始输入中的叶节点而言，比较次数的期望至少为$n\log_3 n$，即$\Omega(n\lg n)$。

c

这个匹配算法如下进行：在$n$个蓝色水壶中随机选择一个出来，假设为$bi$，然后将每个红色水壶逐个和$b_i$比较，并且按照比较结果分别归类到小于，等于，大于三部分。其中等于的那一部分恰好仅有一个，与$b_i$匹配，假设其为$r_i$。那么此时划分出了小于部分$r{1:i-1}$，大于部分$r{i+1:n}$。那么接下来使用$r_i$同样对剩下的$n-1$个蓝色水壶进行比较和划分，假设小于部分为$b{1:i-1}$，大于部分为$b{i+1:n}$。那么当前步骤总共花费了$2n-1=\Theta(n)$次比较。接下来分别对$(r{1:i-1},b{1:i-1}),(r{i+1:n},b_{i+1:n})$进行递归操作即可。

由于这个比较过程的行为和算法RANDOMIZED-QUICKSORT完全一致，因此期望比较次数为$O(n\lg n)$。

当每次选到的蓝色水壶都是当前堆中最大或者是最小的一个，那么比较次数将达到最大，为$\displaystyle{\sum_{i=1}^n (2i-1)=n^2=\Theta(n^2)}$次。

8-5

a

此时式子可以转化为$A[i]\le A[i+1]$，即有序。

b

其中一个为$\langle6, 1, 7, 2, 8, 3, 9, 4, 10, 5\rangle$。

c

整个不等式两边同乘$k$，得到$\displaystyle{\sum{j=i}^{i+k-1} A[j]\le \sum{j=i+1}^{i+k} A[j]}$。消去中间项$A[i+1],A[i+2],\dots,A[i+k-1]$，最终得到$A[i]\le A[i+k]$。

d

这个算法将使用改进的快速排序算法QUICKSORT作为子程序进行排序，其平均、最坏时间复杂度为$O(n\lg n)$。

K-SORTED(A, n, k)
  for i = 1 to k
    let B be new array
    for j = i to n by k
      INSERT(B, A[j])
    QUICKSORT(B, B.size)
    p = 0
    for j = i to n by k
      p = p + 1
      A[j] = B[p]

算法K-SORTED将数组$A$均匀地划分了$k$块，每块的长度为$\Theta(n/k)$。那么对每一段数组使用算法QUICKSORT进行排序，其时间复杂度为$O(n/k\lg (n/k))$。将这$k$段进行综合，那么最终时间复杂度为$k\cdot O(n/k\lg (n/k))=O(n\lg (n/k))$。

e

我们可以将数组$A$均匀地拆分成$k$个有序的，其中第$j$个数组为$\langle A[j],A[j+k],A[j+2k],\dots\rangle$，这些数组的长度总和为$n$。接下来，使用题目6.5-11对$k$个有序数组进行$k$路归并的算法（基于堆排序实现），即可以以$O(n\lg k)$的时间复杂度对$k-$排序算法进行排序。

f

算法K-SORTED将数组$A$均匀地划分了$k$块，每块的长度为$\Theta(n/k)$。那么对每一段数组使用算法QUICKSORT进行排序，其时间复杂度同样有下界$\Omega(n/k\lg (n/k))$。将这$k$段进行综合，那么最终整个算法K-SORTED有下界$k\cdot \Omega(n/k\lg (n/k))=\Omega(n\lg (n/k))$。舍弃常数$k$后，即为$\Omega(n\lg n)$。

8-6

a

如果两个数组长度为$n$的数组是有序的（即对于数组$\langle1,2\rangle$，划分$\langle[1],[2]\rangle$和$\langle[2],[1]\rangle$视为不同的划分），那么一共有$\dbinom{2n}{n}$种划分方式。

b

至少$\dbinom{2n}{n}$个叶节点的树的高度$h$满足$2^h\ge l\ge \dbinom{2n}{n}$，可以得到$h\ge \lg \dbinom{2n}{n}$。根据斯特林公式，可以将值$\dbinom{2n}{n}$如下进行近似：

$\begin{aligned}
\dbinom{2n}{n}&=\dfrac{\sqrt{4\pi
n}\cdot\left(\dfrac{2n}{e}\right)^{2n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{\left(\sqrt{2\pi
n}\cdot\left(\dfrac{n}{e}\right)^{n}\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\right)^2}\
&=\dfrac{2\sqrt{\pi
n}\cdot\left(2n\right)^{2n}\cdot\dfrac{1}{e^{2n}}}{2\pi n\cdot
n^{2n}\cdot \dfrac{1}{e^{2n}}}
\cdot\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\
&=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot
\left(1+\Theta\left(\dfrac{1}{n}\right)\right)\
&=\dfrac{2^{2n}}{\sqrt{\pi n}}\cdot
\left(1+O\left(\dfrac{1}{n}\right)\right) \end{aligned}$

那么可以得到$h\ge 2n - \Theta(\sqrt{n})$，即$h\ge 2n-o(n)$。由于这个决策树的高度至少为$2n-o(n)$，因此比较次数至少为$2n-o(n)$。

c

不失一般性，假设$A[i],B[j]$是原本在序列$A,B$中的两个元素，并且合并后，$B[j]$紧接在$A[i]$的后面。那么在合并过程中，如果不对$A[i]$和$B[j]$进行比较，那么将无法确定$A[i]$和$B[j]$在合并的序列后哪一个数在前面，哪一个数在后面，那么忽略掉这两个数，哪怕是之后的所有数$A[i+1:],B[j+1:]$相互都进行比较了，仍然无法确定出一个有序的序列。因此$A[i]$和$B[j]$必须相互进行比较。

d

每一次迭代，两个序列中的其中一个数将会被安排位置。由于一共有$2n$个数，因此至少需要进行$2n-1$次比较，才能够确定出整个有序序列。当$A=\langle1,3,\dots,2n-3,2n-1\rangle,B=\langle2,4,\dots,2n-2,2n\rangle$时，按照题目8-6-c的结论，比较次数将会达到$2n-1$的最大值。

8-7

a

由于$A[p]$是最小的无法排序到正确的位置的元素，那么说明小于$A[p]$的所有元素都已经排序到了正确的位置。而$A[q]$却占据了$A[p]$原有的位置，此时$A[q]$放置的位置也是不正确的，那么说明$A[q]\ge A[p]$。如果$A[q]=A[p]$，那么序列的有序性不会受到影响，这个位置也是$A[q]$的正确位置。因此仅存在$A[q]>A[p]$的可能性。

根据数组$B$的定义，$A[p]\le A[p]$必定成立，所以$B[p]=0$；由于$A[q]>A[p]$，所以$B[q]=1$。

b

运行算法$X$后，如果$A[p]$排序后没有到达正确的位置，那么说明$A[p]$排序后的位置$p’$位于比真正位置的$q’$靠后，即$p’>q’$。

更进一步的说明：算法$X$是不经意比较-交换排序算法，算法$X$内部是将子程序COMPARE-EXCHANGE作为一系列指令，直接对数组进行操作。也就是说，算法$X$没有分支判断结构，循环结构也可以转化为顺序结构。舍去循环结构后，算法$X$的伪代码将会是如下的样子：

X(A, n)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  COMPARE-EXCHANGE(A, ?, ?)
  ...

因此，本题的证明思路是，比较数组$A$和由$A$构造出来的数组$B$在运行这个算法$X$上的行为是一致的。

以下讨论三种情况：

1. $A[i],A[j]\le A[p]$，那么有$B[i]=B[i]=0$。如果$A[i]>A[j]$，那么调用COMPARE-EXCHANGE(A, i, j)时，$A[i]$和$A[j]$将会被交换，此时$B[i]=B[j]=0$；虽然调用COMPARE-EXCHANGE(B, i, j)不会真正交换，但是并不影响调用完成后保持$B[i]\le B[j]=0$的性质，我们可以视为$B[i]$与$B[j]$发生了交换。如果$A[i]\le A[j]$，那么无论调用COMPARE-EXCHANGE(A, i, j)还是COMPARE-EXCHANGE(B, i, j)，$A[i]$与$A[j]$以及$B[i]$与$B[j]$都不会发生交换。因此，当$A[i],A[j]\le A[p]$时，算法$X$中针对这一类满足$A[i],A[j]\le A[p]$的指令COMPARE-EXCHANGE(A, i, j)和COMPARE-EXCHANGE(B, i, j)的行为是一致的。

2. 同样的，当$A[i],A[j]> A[p]$，那么有$B[i]=B[i]=1$。对这类满足$A[i],A[j]>A[p]$的指令的分析和第1种情况完全相同，只是$B[i]=B[j]=1$。故有结论：当$A[i],A[j]> A[p]$时，算法$X$中针对这一类满足$A[i],A[j]>A[p]$的指令COMPARE-EXCHANGE(A, i, j)和COMPARE-EXCHANGE(B, i, j)的行为是一致的。

3. 当$A[i]\le A[p],A[j]>A[p]$时，$B[i]=0,B[j]=1$，此时调用COMPARE-EXCHANGE(A, i, j)和COMPARE-EXCHANGE(B, i, j)时，都不会发生交换；当$A[i] > A[p],A[j]\le A[p]$时，$B[i]=1,B[j]=0$，此时调用COMPARE-EXCHANGE(A, i, j)和COMPARE-EXCHANGE(B, i, j)时，都会发生交换。

因此，对于数组$A$和数组$B$，对于任意一条COMPARE-EXCHANGE指令，可以看作要么$A[i]$和$A[j]$与$B[i]$和$B[j]$都发生交换，要么$A[i]$和$A[j]$与$B[i]$和$B[j]$都不发生交换，行为是一致的。最终，由于$A[p]$不在原来的位置$q’$上，在$p’$上，那么类似的，对$B$运行算法$X$后，有$B[p’]=0,B[q’]=1$；由于$p’>q’$，因此算法$X$未能对数组$B$完成排序。

c

因为奇数步骤才对数组$A$的元素进行排序，此时使用的排序算法中将会对数组$A$中的元素进行访问，并且进行交换。而偶数步骤中，仅仅是涉及了对数组$A$本身形状的变换，并没有对数组元素进行操作。事实上，偶数步的操作仅仅是对数组元素的位置进行重新排列，因此在每个步骤，我们可以列出一个映射$f$，表示每个旧位置到新位置的变换，然后在下一步奇数步骤上执行排序时，使用的排序指令是经过映射变换后的数组的下标。

例如，一开始输入的数据的下标如下：

1  2  3
4  5  6
7  8  9
10 11 12
13 14 15
16 17 18

那么在第3步中，执行的每行排序算法中将会包含指令：COMPARE-EXCHANGE(A, 1, 2), COMPARE-EXCHANGE(A, 1, 3), COMPARE-EXCHANGE(A, 2, 3)。

经过第2个步骤的变换后，对应数的下标位置如下：

1  7  13
2  8  14
3  9  15
4  10 16
5  11 17
6  12 18

那么在第3步中，执行的每行排序算法中将会包含指令：COMPARE-EXCHANGE(A, 1, 7), COMPARE-EXCHANGE(A, 1, 13), COMPARE-EXCHANGE(A, 7, 13)。

因此本质上这个列排序算法$X’$仍然可以视为是一系列COMPARE-EXCHANGE指令的集合，因此它可以视为一个不经意比较-交换排序算法。

d

在第一个步骤完成后，第$j$列从上到下都是由一些$0$紧跟着一些$1$。如果第$j$列上面有$cj$个$0$，那么第$j$列下面有$r-c_j$个$1$。由于每一列排完序后，$0$和$1$相邻的坐标个数最多只有$1$个，因此将每一列的$r$个元素均匀划分成$s$个区间后，前$\left\lfloor\dfrac{c_j}{s}\right\rfloor$个区间全部为$0$，后$\dfrac{r}{s}-\left\lfloor\dfrac{c_j}{s}\right\rfloor-1$个区间全部区间全部为$1$。那么第2个步骤完成后，整个矩阵至少有$\displaystyle{\sum{j=1}^s\left\lfloor\dfrac{cj}{s}\right\rfloor}$个全$0$行，至少$\displaystyle{\sum{j=1}^s\left\lfloor\dfrac{r}{s}-\left\lfloor\dfrac{cj}{s}\right\rfloor-1\right\rfloor}=r-\sum{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor-s$个全$1$行。

那么接下来每一列的排序可以进行如下变换：将$\displaystyle{\sum{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor}$个全$0$行向顶部转移并合并，形成$\displaystyle{\sum{j=1}^s\left\lfloor\dfrac{cj}{s}\right\rfloor}$个全$0$干净行；将$\displaystyle{r-\sum{j=1}^s\left\lfloor\dfrac{cj}{s}\right\rfloor -s}$个全$1$行。向底部转移并合并，形成$\displaystyle{r-\sum{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor -s}$个全$1$干净行。剩下的至多$s$行都是脏行，直接对这个$s\times s$的区域每一列进行列排序即可。可以发现这种操作和对整个列的$r$个元素进行排序是相同的（因为之前对全$0$行和全$1$行的操作保证了顶部已经都是$0$，底部都是$1$。）

因此，最终结论是至少$\displaystyle{\sum{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor}$行的全$0$干净行，至多$s$行的脏行，以及至少$\displaystyle{r-\sum{j=1}^s\left\lfloor\dfrac{c_j}{s}\right\rfloor -s}$行的全$1$干净行。

e

按列优先的方式读取步骤4后得到的矩阵，相当于是按行优先读取步骤3后得到的矩阵。正如题目8-7-d的结论，中间有一个$s\times s$的脏区域，因此按行优先的顺序读取步骤3得到的矩阵后，将会有一个长度至多为$s^2$的脏区域序列，前面的是全$0$干净区域，后面的是全$1$干净区域的序列。

f

由于$r\ge 2s^2$成立。因此，题目8-7-e中间的$s^2$个脏区域序列最多处在$2$个不同的列中。接下来分别考虑两种情况。

• 如果这个$s^2$的脏区域序列横跨在两个不同的列中，那么其起点必定在前一列的下半部分，其终点必定在后一列的上半部分；步骤5对这两个列排完序后，前一列的起点会有所继续下降，后一列的终点会有所上升，但是起点在前一列的下半部分，其终点在后一列的上半部分这个事实仍然不变。第6行的操作则是将前一列的下半行接在后一列的上半行前面，形成一个新列，此时整个脏区域必定在同一列。步骤7则继续对每一列进行排序，这对其它干净列没有影响；对含有脏区域的一列，将会重新排序。步骤7完成后，只有这一列会产生一个$0,1$相邻的坐标。步骤8将整个序列还原，按列优先读取并不会改变所有数的位置，此时将产生一个全排序的0-1输出。

• 如果这个$s^2$的脏区域序列仅在同一列中，那么步骤5的排序完成后就可以停止了，只有这一列会产生一个$0,1$相邻的坐标。步骤6和7的变换和排序不会产生任何改变，因为步骤6的操作完成了，每一列就已经是单调有序的，步骤7的列排序操作是无用的。步骤8则是将数组还原。最终产生一个全排序的0-1输出。

因此，这个不经意比较-交换排序算法可以对任何一个只含0和1的序列正确排序，那么根据0-1排序引理，这个算法可以对任意输入值的序列进行排序。

g

如果$s\nmid r$，那么按照步骤2的变换，前一列的最后一个数（如果不是全$0$，那么最后一个数必定是$1$）将会和后一列的第一个数（如果不是全$0$，那么第一个数必定是$0$）有可能在某一行中是相邻的，这种接触最多有$s-1$个（第$1$列和第$2$列的首尾相接，第$2$列和第$3$列的首尾相接……第$s-1$列和第$s$列首位相接）。再加上题目8-7-d的分析结果（每一列中，$0$和$1$相邻的坐标个数最多只有$1$个），故至多有$2s-1$个行组成的脏区域。

因此步骤4完成后，中间会有一个最多$(2s-1)s$个元素组成的脏区域。为了保证这些元素最多只占半列的位置，使得步骤5-8正确进行，$r$需要满足$r\ge 2\cdot(2s-1)s$，即$r\ge 4s^2-2s$。

h

将$r$行的序列填充到$r’$行，使得$s\mid r’$即可。填充的内容是$(r’-r)\times s$的$+\infty$。填充后的矩阵是$r’\times s$的大小，并且满足$r’\ge r\ge 2s^2$。因此将上面的算法作为子程序进行排序。步骤8完成后，将最后的$(r’-r)s$个$+\infty$舍弃。

证明：基于原排序算法的正确性，最后$(r’-r)s$个元素必为$+\infty$，舍去这些$+\infty$后将得到原本正确的排序结果。因此这个新算法是正确的。