題目來源：Merge Sorted Array

問題：
給予兩個已經排序過的陣列A、B，請試著將 陣列B 合併 到 陣列A 裡去。
你可以假設 陣列A 擁有足夠的空間可以容納 陣列B 裡的元素（ 也就是 陣列A 的大小會大於等於 m + n），A、B陣列的大小分別為 m 和 n 。

想法
既然題目說明了這兩個陣列已經排序過了，所以我們只要去比較大小再合併就好了。可是，如果我們從 index 0 開始的話，勢必會遇到一個問題，那就是 插入 元素的問題，這樣一來是必須要一個暫存的地方來存放。不過這樣做效能不是很好！
所以，我們可以換個想法，從尾端開始比較。這樣就不會有 插入 元素的問題，在空間複雜度和時間複雜度上也會有所提升。

題目說，A的陣列大小會大於或等於A+B的陣列大小，因此我們可以不用擔心 IndexOutOfRangeException 的問題，就直接從尾端開始吧！

合併兩個已排序陣列

public void Merge(int[] A, int m, int[] B, int n)
{
    // 因為 A 有 m 個元素，B有 n 個元素
    while (m + n > 0)
    {
        // 當 A 和 B 都有元素時
        if (m > 0 && n > 0)
        {
            // 若 A 的最後一個大於 B 的最後一個
            // 因為 array index 是從 0 開始, 所以 假設有 5 個元素
            // 則第5個元素的 index 就是 4 ( 5-1 )
            if (A[m-1] > B[n-1])
            {
                A[m + n - 1] = A[m-1];
                m -= 1;
            }
            else // 若 B 的最後一個比 A 的最後一個大
            {
                A[m + n - 1] = B[n-1];
                n-=1;
            }
        }
        else if (n > 0) // 當 A 比較完了，剩 B
        {
            A[m + n - 1] = B[n-1];
            n -= 1;
        }
        else // 當 B 比完了，剩 A，不過 A 不用再從自己搬到自己，所以直接減掉 index 即可
        {
            m -= 1;
        }
        
    }
}

如果還是沒感覺，可以看一下這個例子：
假設
A = [1, 3, 5, 7, -1, -1, -1, -1], m = 4 (因為題目說，陣列A 的實際大小會大於等於 m+n，所以我先假設多出來的空間是-1)
B = [2, 4, 6, 8], n = 4

首先 m+n 是 8, m=4, n=4
第一輪: A[m-1] 比 B[n-1] 小，所以把 B[n-1] 放到 A[m+n-1] (記住，index 是從0開始，所以要減 1)
=> A = [1, 3, 5, 7, -1, -1, -1, 8]

目前的 m=4, n=3
第二輪: A[m-1] 比 B[n-1] 大，所以把 A[m-1] 放到 A[m+n-1]
=> A = [1, 3, 5, 7, -1, -1, 7, 8]

以下就以此類推就行了!

到目前為止應該有感覺了吧！！ Good!