# 閱讀筆記： Bottom-up Mergesort
## Notations

* **比較次數**
* $C_{b,td}(N)$ ： 最佳狀況下， top-down 演算法的比較次數
* $C_{w,td}(N)$ ： 最糟狀況下， top-down 演算法的比較次數
* $C_{a,td}(N)$ ： 平均狀況下， top-down 演算法的比較次數
* $c_{n,m}$ ： 在一次 $(n,m)$ 合併中的比較次數

* **機率與期望值**
* $P\{\cdot\}$ 機率
* $E\{\cdot\}$ 期望值
## 歷史回顧
### 從週期函數分析 Top-down 合併排序

Bottom-up Mergesort 於引言中最後一段有說明：
> this paper may be seen the complement to [[Flajolet, Golin]](#1) for the bottom-up algorithm.

這篇文章的架構是建立在 [[Flajolet, Golin, 1]](#1) 對 Top-down 合併排序的係數做漸進分析（ asymptotics ）得到一個較為精準的複雜度分析。

Flajolet 和 Golin 的作法是將分治法遞迴：$$f_N=f_{\lfloor \frac{N}{2} \rfloor}+f_{\lceil \frac{N}{2} \rceil}+e_N,\quad N\geq 2,\quad f_1=0$$， $e_N$ 根據不同問題而定。

藉由複變函數分析改寫成帶有一週期函數 $P(x)$ 的形式：$$N\log_2N+NP(\log_2N)+o(N)$$

Top-down 合併排序虛擬碼，摘錄自 [[1]](#1)：

/* Flajolet, Philippe, and Mordecai Golin.
 * Mellin transforms and asymptotics: the mergesort recurrence.
 * */
Algorithm MergeSort(A[1,..,N])
if length of A > 0 then
    MergeSort(A[1,...,floor(N/2)]);
    MergeSort(A[ceil(N/2),...,N]);
    Merge(A[1,...,floor(N/2)],A[ceil(N/2),...,N],B[1,...,N])

/* Merges sorted lists A and B into list C
 * and then copies the result into list D
 * */
 
Procedure Merge(A, B, C);

i=size(A), j=size(B);
// Compare largest elements in each list
while(i > 0, j > 0) do
    if(A[i] > B[j])
        then {C[i+j]=A[i];i=i-1;}
        else {C[i+j]=B[j];j=j-1;}

// Move contents of nonempty list over to C
S=i+j;
if(i > 0)
    then for k=S downto 1 do C[k]=A[k];
    else for k=S downto 1 do C[k]=B[k];
for j=1 to i+j do D[k]=C[k];

以下是基於合併過程中三種情況下的比較次數：

* Worst Case
$<i,j>$ 合併，最糟情況下 $i+j$ 長度的串列需要做 $i+j-1$ 次比較，在非空串列中剩餘的元素個素 $S=1$ ，故在此狀況下 $e_N=N-1$：
$$T(N)=T\left(\left\lfloor \frac{N}{2} \right\rfloor\right)+T\left(\left\lceil \frac{N}{2} \right\rceil\right)+N-1, \quad N\geq 2, \quad T(1)=0.$$
* Best Case
$<\left\lceil \frac{N}{2} \right\rceil, \left\lfloor \frac{N}{2} \right\rfloor>$ 合併，，故在此狀況下 $e_N=\left\lfloor \frac{N}{2} \right\rfloor$：
$$Y(N)=Y\left(\left\lfloor \frac{N}{2} \right\rfloor\right)+Y\left(\left\lceil \frac{N}{2} \right\rceil\right)+\left\lfloor \frac{N}{2} \right\rfloor, \quad N\geq 2, \quad Y(1)=0.$$
* Average Case
討論平均狀況，需要引入機率的概念來處理。令 $x$ 為非空串列中剩餘的元素個數，以 $x$ 元素形成的集合為 $X$ 。 $X$ 非空集合，因為最佳 $x=\left\lfloor \frac{N}{2} \right\rfloor$ 與最糟 $x=1$ 狀況皆存在於 $X$ 中。
而對於一個 $i+j$ 長度的串列，要將其分割成長度為 $i$ 子串列與長度為 $j$ 子串列，總共有 $\displaystyle{i+j\choose i}={i+j\choose j}$ 種分割方式。
則機率分布（ probability distribution ）為：
$$Pr(X\geq x)=\dfrac{\displaystyle{i+j-x\choose i}+\displaystyle{i+j-x\choose j}}{\displaystyle{i+j\choose i}}.$$ 期望值： $$E(X)=\dfrac{i}{j+1}+\dfrac{j}{i+1}.$$ 在$<\left\lceil \frac{N}{2} \right\rceil,\left\lfloor \frac{N}{2} \right\rfloor>$ 合併中需要的比較次數為 $e_N=N-\gamma_N$ 此處根據期望值可得 $$\gamma_N=\dfrac{\left\lfloor \frac{N}{2} \right\rfloor}{\left\lceil \frac{N}{2} \right\rceil+1}+\dfrac{\left\lceil \frac{N}{2} \right\rceil}{\left\lfloor \frac{N}{2} \right\rfloor+1}$$ 故平均比較次數的遞迴式為：
$$U(N)=U\left(\left\lfloor \frac{N}{2} \right\rfloor\right)+U\left(\left\lceil \frac{N}{2} \right\rceil\right)+N-\gamma_N, \quad N\geq 2, \quad U(1)=0.$$

假設串列有 $N$ 個元素， top-down 合併排序的比較次數有界：
$$
\sum_{i=1}^{N-1} \nu(i) \leq C_n \leq \lceil \log_2 N \rceil N - 2^{\lceil \log_2 N \rceil} + 1
$$

此處 $\lceil \cdot \rceil$ 為上取整函數（ ceil function ），$\nu(i)$ 為 $i$ 以二進位表示法下 $1$ 的數量。實際演算法見[2024q1 第 4 週測驗題 population count](https://hackmd.io/@sysprog/linux2024-quiz4)

<!-- 以 GeoGebra 繪製 $A(x)$
<iframe src="https://www.geogebra.org/calculator/vn4wua5e?embed" width="700" height="350" allowfullscreen style="border: 1px solid #e4e4e4;border-radius: 4px;" frameborder="0"></iframe> -->

### 針對合併排序中週期函數的分析

[[1, Theorem 1]](#1)以週期函數表示最糟比較次數：
$$
N \log_2{N} +NA(\log_2{N})+1
$$

此處 $A(x) = 1 -\{x\}-2^{1-\{x\}}$ 是週期為 $1$ 的週期函數。 $\{\cdot\}\equiv x - \lfloor x \rfloor$ ，當 $x$ 大於 $0$ 。 參見 [Fractional part](https://en.wikipedia.org/wiki/Fractional_part) 。

**證明：**
只要證明
$$
N \log_2{N} +NA(\log_2{N})+1
$$

與
$$
\lceil \log_2{N} \rceil N - 2^{\lceil \log_2{N} \rceil} + 1
$$

兩者等價即可。

把上取整數函數改寫成：
$\begin{align}
\lceil \log_2 N \rceil
&= \log_2 N - \log_2N + \lceil \log_2 N \rceil \\
&= \log_2 N - \left(\log_2 N - \lceil \log_2 N \rceil \right) \\
&= \log_2 N - \left(\log_2 N - (\lfloor \log_2 N \rfloor+1) \right) \\
&= \log_2 N + 1 - \{ \log_2 N\}
\end{align}$

最後得到
$\begin{align}
\lceil \log_2 N \rceil N - 2^{\lceil \log_2 N \rceil} + 1
&= \lceil \log_2 N \rceil N - 2^{\log_2 N + 1 - \{ \log_2 N\}} +1 \\
&= \lceil \log_2 N \rceil N -N2^{1 - \{ \log_2 N\}}+1 \\
&= N\left(\log_2 N + 1 - \{ \log_2 N\} -2^{1 - \{ \log_2 N\}}\right) +1 \\
& = N \log_2N +NA(\log_2N)+1
\end{align}$

### 合併排序法最佳與最糟比較次數的表示法
[A000788 - OEIS](https://oeis.org/A000788)
[A003071 - OEIS](https://oeis.org/A003071)查看這個數列的形式

## 參考資料

<a id="1">[1]</a> Flajolet, Philippe, and Mordecai Golin. "Mellin transforms and asymptotics: the mergesort recurrence." Acta Informatica 31 (1994): 673-696.

[wikipedia: Sorting number](https://en.wikipedia.org/wiki/Sorting_number)
[](https://oeis.org/A003071)