# MergeSort 的 Worst case 探討

先來看一般 mergesort

假設有一個 size 為 8 的陣列, [2 4 5 1 6 7 9 0]

會先進行 divide :

original: [2 4 5 1 6 7 9 0]

pass 1: [2 4 5 1]   [6 7 9 0]

pass 2: [2 4]    [5 1]    [6 7]    [9 0]

pass 3: [2]   [4]   [5]   [1]   [6]   [7]   [9]   [0]

再來進行合併:

original: [2]   [4]   [5]   [1]   [6]   [7]   [9]   [0]

pass 1: [2 4]    [1 5]    [6 7]    [0 9]

> 這裡有 4 次比較

pass 2: [2 4]    [1 5]    [6 7]    [0 9]

> 首先在 [2 4]    [1 5] 的合併中，2 會有 2 次比較，4 會有 1 次比較，共 3 次比較次數;
再來是 [6 7]    [0 9] 的合併， 6 會有 2 次比較，7 會有 1 次，共 3 次比較次數，兩邊加起來共 6 次。

pass 3: [1 2 4 5]    [0 6 7 9]

> 1 會有 2 次比較(跟 1 和 6比) -> [0 1]
> 2 會有 1 次比較(跟 6 比) -> [0 1 2]
> 4 會有 1 次比較(跟 6 比) -> [0 1 2 4]
> 5 會有 1 次比較(跟 6 比) -> [0 1 2 4 5]
> 剩下的右邊直接加入，共 5 次比較次數

3 次 pass 中加起來共產生了 4+6+5 = 15 次比較次數

這是一個隨機的例子而已，接下來會特地設計一些數字來找出 worst case。

## Descending order

既然 Ascending order 會是 Mergesort 的 best case ， 那反過來說，Descending order 會不會是 worst case 呢?

original: [8 7 6 5 4 3 2 1]

經過 divide 環節後 [8]   [7]   [6]   [5]   [4]   [3]   [2]   [1]

pass 1: [7 8]    [5 6]    [3 4]    [1 2]

> pass 1 中共有 4 次比較。

pass 2: [5 6 7 8]    [1 2 3 4]

> 首先 [7 8]    [5 6] 的合併中，會產生 2 次比較(7跟 5和6比)，而 [3 4]    [1 2] 合併中，也會產生 2 次比較(3 跟1和2比)，pass2 中共有 4 次比較

pass 3: [1 2 3 4 5 6 7 8]

> 5會分別跟右邊的 1 2 3 4 比過，然後結束合併，共產生 4 次比較

所以 3 次 pass 下來總共是 4+4+4 = 12 次比較，可以發現次數比前面隨便舉的數字排列還要低，關鍵就出在兩邊欲合併的串列中每個數字的是否都有比較到。

如果是原本的 Descending order，再進行完 divide 要進行合併時，右子陣列的所有元素會比左子陣列小，因此合併時只需依序取右子陣列元素，無需頻繁比較。

透過前面兩個 case 可以發現，不管是第幾個 pass，當兩個要合併的串列裡面的數字大小是 **交錯** 排序的時候，那一次的合併會產生較高的合併次數，因為陣列中的至少有比較過 1 次的數變多了，所以比較不會出現一邊率先被合併完，而另一邊還剩很多數就直接合併進去的情況，所以最差的情況，需要進行 n-1 次的比較才能得到排序好的 n 個數的陣列。

## Number of comparisons

假設輸入陣列的大小為 $n = 2^k$，而整個 divide 的過程可以看做是一個高度為 $log_2n$ 的平衡二元樹，$n$ 為該樹的節點數。

#### Divide 階段

可以將第 0 層視為是 root
第 1 層則是經過第 1 次 divide，將原本的陣列拆分為 2 個大小為 $\frac n{2}$ 的陣列
以此得知，第 $i$ 層( $i$ 從0開始)會有 $2^i$ 個大小為 $\frac {n}{2^i}$ 的陣列。

#### 合併階段

第 $i$ 層要合併時，每個合併都會兩個 $\frac{n}{2^i}$ 大小的陣列參與，若是最佳狀況，則只會有一邊的元素率先合併完成，所以只須計算一邊的比較次數，裡面每個元素各比 1 次，所以是 $\frac{n}{2^i}$ 次比較，所以第 i 層共有 $\frac{2^i}2 \times \frac{n}{2^i}$ 次比較。

而整個二元樹的比較次數就為 $\sum_{i=1}^{log_2n} \frac{2^i}2\times \frac{n}{2^i} = \frac{n}2log_2n$。

如果是交錯的情況下，則每個合併都會產生 $2 \times \frac n{2^i}-1$ 次比較。

第 i 層會有 $\frac{2^i}2$ 次合併，所以該層的比較次數為 $\frac{2^i}2 \times (2 \times \frac n{2^i}-1) = n - 2^{i-1}$

而整個二元樹的比較次數就為

$\sum_{i=1}^{log_2n} n - 2^{i-1} = nlog_2n - (n - 1) = nlog_2n - n +1$ 。

## 如何產生 worst case

因為前面有說過，worst case 是元素交錯，而不單單只是隨便的打亂，所以要刻意製造一些交錯的排列。

我們對一個已將排序完成的陣列做一些操作，將陣列中奇數項和偶數項分別置於陣列的左右邊，可以想像成兩個新的陣列，然後兩個陣列在各自依照前面的操作遞迴下去。

void gen_worst(int *src, int *dst, int n)
{
    if (n <= 1) {
        if (n == 1) dst[0] = src[0];
        return;
    }
    
    int half = n/2;
    int *left = (int *)malloc(half * sizeof(int));
    int *right = (int *)malloc((n - half) * sizeof(int));
    
    for(int i=0, l=0, r=0;i<n; i++){
        if (i%2 == 1){
            left[l++] = src[i];
        }
        else{
            right[r++] = src[i];
        }
    }
    gen_worst(left, dst, half);
    gen_worst(right, dst+half, n-half);
    
    free(left);
    free(right);
}

但這樣必須依賴已經排好序的陣列，試看看能不能有自行生成的方式。

參考這篇文章: [When will the worst case of Merge Sort occur?](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur)

首先將輸入的整數拆成兩個部分 `Top` 和 `bottom`，分別遞迴建構出 `top` 和 `bottom` 的 worst-case 陣列，其中

**top**: 每個元素乘 $2$→ 結果是全為偶數

**bottom**: 每個元素乘 $2$ 後再剪掉 $1$ → 結果是全為奇數

最後把兩部分合併為新陣列。

當輸入為 **4** 時

1. 先拆成兩個部分 -> `[2,1] + [2,1]`
2. 得到 -> `[2, 1 | 2, 1]`
3. `top` 乘上 $2$，`bottom` 乘上 $2$ 再減 $1$ -> `[4,2 | 3,1]`
4. 合併切分好的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *worstCaseArray(int n, int *outputSize)
{
    if (n == 1){
        int *dst = malloc(sizeof(int));
        dst[0] = 1;
        *outputSize = 1;
        return dst;
    }

    int topSize = n / 2;
    int bottomSize = n - topSize;
    int topOutputSize, bottomOutputSize;

    int *top = worstCaseArray(topSize, &topOutputSize);
    int *bottom = worstCaseArray(bottomSize, &bottomOutputSize);
    
    for (int i = 0;i<topSize;++i){
        top[i] *= 2; 
    }
    for (int i = 0;i<bottomSize;++i){
        bottom[i] = bottom[i] * 2 -1; 
    }

    int *wst = malloc(n * sizeof(int));
    memcpy(wst,top, topSize * sizeof(int));
    memcpy(wst+topSize, bottom, bottomSize * sizeof(int));

    *outputSize = n;

    free(top);
    free(bottom);
    
    return wst; 
}

但這樣沒有辦法包含到全部的測資?