摘要：兩個單元素數組的合并實際就是對這兩個數進行了排序，即變為，同樣再對后一組的兩個數歸并排序，即變為，再將兩單元數組歸并成四單元數組即和歸并為。

本周講解兩個50多年前發明，但今天仍然很重要的經典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個軟件系統中都可以找到其中一個或兩個的實現，并研究這些經典方法的新變革。我們的涉及范圍從數學模型中解釋為什么這些方法有效到使這些算法適應現代系統的實際應用的細節。

Mergesort。我們研究 mergesort 算法，并證明它保證對 n 項的任何數組進行排序，最多只能進行 nlgn 次的比較。我們還考慮一個非遞歸的自下而上版本。我們證明，在最壞的情況下，任何基于比較的排序算法必須至少進行 ~nlgn 的比較。我們討論對我們正在排序的對象使用不同的排序以及相關的穩定性概念。

上一篇：基本數據類型
下一篇：快速排序

這章我們討論歸并排序，這是計算基礎中的兩個重要排序算法之一
我們已經對一些算法有了科學全面的認知，這些算法被大量運用在系統排序和應用內排序超過50多年，我們之后所要看到的快速排序更是被在科學和工程中被譽為20世紀10大算法之一

所以歸并排序到底是什么樣的?

基本計劃流程：

將陣列分成兩半

遞歸排序每一半

合并兩半

它的思想其實很簡單, 只要把數組一分為二, 然后再不斷將小數組遞歸地一分為二下去, 經過一些排序再將它們合并起來, 這就是歸并排序的大致思想, 這是人們在計算機上實現的最早的算法之一.
(EDVAC 計算機是最早的通用型計算機之一, 馮諾依曼認為在他的 EDVAC 中需要一種排序算法, 于是他提出了歸并排序, 因此他被公認為是歸并排序之父)

歸并排序的核心就是“并”。所以要理解如何歸并，先考慮一種抽象的“原位歸并”。

也叫 Top-down mergesort. 下邊還有歸并的另一種實現，叫 Bottom-up mergesort.

目標 給定一個數組，它的前一半(a[lo]-[mid]) 和 后一半([mid + 1]-[hi]) 已是排好序的，我們所要做的就是將這兩個子數組合并成一個大的排好序的數組

看一個抽象原位歸并演示

1.在排序之前我們需要一個輔助數組，用于記錄數據，這是實現歸并的最簡單的方式

2.首先將原數組中所有東西拷貝進輔助數組，之后我們就要以排好的順序將它們拷貝回原數組
這時我們需要三個下標：i 用于指向左邊子數組；j 指向右邊子數組；k指向原數組即排好序的數組。

3.首先取 i 和 j 所指數字中取其中小的放入原數組k的位置，當一個被拿走之后，拿走位置的指針 (這次是 j) 和 k 遞增

4.同樣取 i 和 j 中小的那個移向 k 的位置，再同時增加移動位置的指針(這次還是 j 和 k)

以此類推。完整演示地址：在此
這就是一種歸并方式： 用了一個輔助數組，將它們移出來又排好序放回去。
這就是歸并部分的代碼，完全依著之前的演示

public class Merge {

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
/**
 * assertion功能: 方便我們找出漏洞并且確定算法的正確
 * 想確定a[lo] 到 a[mid] 和 a[mid+1] 到 a[hi] 是否已是排好序的
 */
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid + 1, hi);

        //拷貝所有東西進輔助數組
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        /**
         * 完成歸并
         * 初始化 i 在左半邊的最左端
         * j 在右半邊最左端
         * 指針 k 從 lo 開始
         * 比較輔助數組中 i 和 j 誰更小，并將小的那個的值移向 k
         **/
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            //如果 i 走到邊界了，就只將 j 的值都移上去
            if (i > mid) a[k] = aux[j++];
            //如果 j 走到邊界了，就只將 i 的值都移上去
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
        //最后再檢查最終合并后的時候排好序
        assert isSorted(a, lo, hi);
    }

    // 遞歸的 sort 方法
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    // 對外提供接口中 sort 函數
    public static void sort(Comparable[] a) {
        //創建輔助數組
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

完整“原位”歸并代碼：在此

在這個簡單的實現中傳入了 Comparable 類型的原數組 a[] 和 輔助數組 aux[], 還有三個參數 lo, mid, and hi.
lo指向的是兩個將要合并的子數組的頭部 mid指向前一個子數組的末端 所以我們的前提是lo到mid時排好的 從mid+1到hi也是排好的

有了歸并，排序中遞歸的就簡單多了。
sort() 在遞歸調用前先檢查下標，然后像二分查找那樣計算中點值。sort前半部分，再sort后半部分，然后merge
對外提供接口中 sort 函數只接收一個參數，創建輔助數組的任務就交給這個 sort()

這里關鍵在于不要將輔助數組在遞歸的 sort() 中創建, 因為那會多出許多額外的小數組的花費, 如果一個歸并排序效率很低通常都是由這引起 這是一個很直接的實現方式。也是依據了我們看到多次的一個思想--分治法：即解決問題時將其一分為二，分別解決兩個小問題，再將它們合并起來

一般來說Java程序員，認為加入這些 assert 是有益的：

幫助我們發現漏洞

同時也提示了之間的代碼的功能

這個歸并代碼就是很好的例子，如此以代碼的形式加入 assert 語句表明了接下來你想做什么，在代碼最后加上 assert 語句表明了你做了什么。
你不僅確定了代碼的正確，也告訴閱讀代碼的人你所干的事情。

Java 中 asset 語句接受一個 boolean 值。isSorted 函數前面已經寫過了(請回復 -- 基本排序)，如果排好序返回 true，反之返回 false. assert 在驗證到沒正確排序時會拋出異常.

assert 可以在運行時禁用.
這很有用因為你可以把 asset 語句一直放在代碼中, 編程時供自己所需, 禁用后在最終上線程序中不會有額外代碼。因此 assertion 默認是禁用的。出錯的時候人們還可以啟用assertion然后找到錯誤所在。

java -ea MyProgram //啟用 assertions
java -da MyProgram //禁用 assertions(默認)

所以平時最好像之前的例子那樣加入assert語句，并且不讓他們出現在產品代碼中，而且不要用額外的參數來做檢查。

這幅圖顯示了每次調用 merge 時的操作。
我們將一個大的問題對半分，再將其中的一半對半分，對于那些分到不能再分單個元素，我們做的就是兩兩間的比較。
兩個單元素數組的合并實際就是對這兩個數進行了排序，即 M-E 變為 E-M，同樣再對后一組的兩個數歸并排序，即 R-G 變為 G-R，再將兩單元數組歸并成四單元數組,即 E-M 和 G-R 歸并為 E-G-M-R。
同樣再對后兩對歸并(E-S,O-R)，這樣就得到兩個四單元數組(E-G-M-R 和 E-O-R-S), 再歸并得到八單元組(E-E-G-M-O-R-R-S).
右邊的一半也是同理,最終兩個八單元合并,得到最終的結果.
觀察這個軌跡圖對于學習遞歸算法是很有幫助的.

Q. 以下哪種子數組長度會在對長度為 12 的數組進行歸并排序時出現？
A. { 1, 2, 3, 4, 6, 8, 12 }
B. { 1, 2, 3, 6, 12 }
C. { 1, 2, 4, 8, 12 }
D. { 1, 3, 6, 9, 12 }

運行時間估計：

可以將歸并排序用在大量數據中，這是個非常高效的算法。如表中所示，如果要對大量數據進行插入排序，假設有十億個元素，用家里的電腦要花幾個世紀。就算目前的超級計算機也要花費一個星期或更多。
但是擁有一個高效的算法，你對十億個元素排序，家用電腦也只需半小時，超級計算機更是一瞬間即可完成，一些小型的問題PC也可迅速完成。因此要么你有很多錢和時間，要么你要有一個好的算法。這是我們在這門課中的核心主題，即一個好的算法遠比差的算法所花時間和金錢高效得多。

這些數學的東西才能展示出分治法的強大 展示出歸并算法如何在 nlogn 時間中解決了選擇排序和插入排序需要 N^2 時間才能解決的問題。

比較次數

命題：對于大小為 n 的數組，歸并排序需要最多 nlogn 次比較 和 6nlogn 次數組訪問

證明：證明這個結論就是需要從之前的代碼中得出遞推關系式, 這便是代碼所反映的數學問題。
如果對 n 個元素排序，用關于 n 的函數 C(n) 來表示需要比較的次數

歸并時左半部分和右半部分元素個數就用 n/2 上取整 和 n/2 下取整來表示, 這就是兩個子數組的大小. 因為我們遞歸地調用函數, 所以括號里就是每次遞歸時分割后子數組的大小, 于是整個一項就是子數組中這些數排序需要的比較次數.
對于左半部分比較次數, 就是關于 n/2 上取整的函數 C(n/2); 對于右邊同理. 二合并時我們需要至多 n-1 次比較
因為如果左右沒有一邊提前排完,就需要 n-1 次比較. 這也只是 n 大于等于 1 的情況. 如果只有一個單元, 是不需要任何比較的, C(1) = 0.
于是這個從代碼中考查得來的公式就能精確計算所需要的比較次數上界.

關于這些求這些復雜公式的通項，具體可以回顧離散數學

我們可以看一下當 n 為 2 的冪時的情況(但結論是對 n 為任意數都成立的, 我們可以通過數學歸納法來證明)

D(n) = 2 D(n / 2) + n, for n > 1, with D(1) = 0. 

和前面相似的遞推關系式, 我們將展示一種證明方法.

分治遞歸
都假設 n 為 2 的冪次，那 n^2 除以二也是 2 的冪, 這是顯然的。
命題： 當 n 是 2 的冪次時的情況, 即，如果 D(n) 滿足 D(n) = 2 D(n / 2) + n，當 n > 1, 當且僅當 n=1 時 D(1)=0，通項 D(n) = nlogn.

圖示法

!

可以看到每次歸并，對于一整層的比較次數都是 N 次，所以共有多少層? 將 N 不斷除 2 一直到等于2，一共有 logN 層(以2為底), 所以總共有 NlogN 次比較。歸并的全部開銷就在于比較次數, 也就是 NlogN. 這就是用圖示法來計算遞推式.

數組訪問

命題：對于大小為 n 的數組，歸并排序使用 ≤ 6nlgn 個數組訪問來排序數組

對于數組訪問次數的計算相似, 只是在歸并的時候后面加上的是 6n

將 a 數組復制到 aux 數組：數組訪問 2 n 次; 如果 less() 方法運行了 2 n 次，如果每次 less() 都返回 true, 那么又需要 2 * n 次來將輔助數組中的值儲存回原數組，所以總共 6n 次

A(n) ≤ A(?n / 2?) + A(?n / 2?) + 6n for n > 1, with A(1) = 0. 

Key point. 任何具有以下結構的算法都需要 nlogn 時間

命題: Mergesort 使用與 n 成比例的額外空間
歸并排序的一大特點就是它需要隨 n 增大而增大的額外空間, 因為有那個額外的輔助數組.

證明： 對于最后一次合并，數組aux []的長度必須為n。
我們將兩個子數組看似原地排序, 但實際上并不是真正的“原地”, 因為我們用到了額外的數組。

如果使用 ≤ clogn 的額外內存，則排序算法就是原地排序，例如：
插入排序，選擇排序，和 希爾排序

這些排序算法不需要額外空間，但歸并排序你只能放一半，另一半要留給輔助數組。

如果你覺得現在所學的太簡單，而在思考一種真正的原地歸，其實人們已經有一些方法來完成，但只是理論上可行，實踐太過繁瑣，而沒有能被運用，也許存有簡單的方式實現原地歸并，這就有待我們去發現。
不過現在有些切實可行的改進，能讓歸并算法變得高效，這就來看一下因為這種技巧也能用于其他算法：

使用數組長度為 ~ ? n 的額外數組 aux[] 代替長度為 n 的額外數組
首先對特別小的數組運用歸并排序太過復雜，比如大小為二三四的數組，歸并它們時調用函數也會有開銷，更糟糕的是不斷地遞歸會分出很多很多小數組，所以第一個改進就是進行切分，對小于某個數值的小數組采用插入排序，這樣能更加有效。 所以加入這一行能讓歸并更快，快大約20%。

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
 //Cutoff to insertion sort for ≈ 7 items.
 if (hi <= lo + CUTOFF - 1)
 {
     Insertion.sort(a, lo, hi);
     return;
 }
     int mid = lo + (hi - lo) / 2;
     sort (a, aux, lo, mid);
     sort (a, aux, mid+1, hi);
     merge(a, aux, lo, mid, hi);
}

第二個對算法的改進可以是當(merge之前)兩個子數組間如果已是有序，便可跳過此輪歸并。判斷這種情況只需判斷前一半最大的數是否小于后一半最小的數，僅此而已，So easy. 因此我們就在歸并前加一句判斷，檢測子數組是否有序，這樣只要在每個歸并前檢測一下，也只需線性復雜度的時間即可完成，這至少在一些情況下是有幫助的

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
     if (hi <= lo) return;
     int mid = lo + (hi - lo) / 2;
     sort (a, aux, lo, mid);
     sort (a, aux, mid+1, hi);
     //are subarrays sorted?
     if (!less(a[mid+1], a[mid])) return;
     merge(a, aux, lo, mid, hi);
}

另一個可以改進的比較費解, 所以只推薦于專業人士.改進在于節省下拷貝到輔助數組的時間(不是空間)。這種改進相當于每一輪遞歸時轉換一下原數組和輔助數組的角色，不過還是需那個輔助數組。代碼如下：

將sort結果放入另一數組，將merge結果合并回原數組，所以遞歸函數同時也完成了交換兩個數組角色的任務，這就意味著不用花時間拷貝元素進輔助數組，就節省下了一點時間。

完整代碼：在此

我們上訴實現的歸并排序是穩定的嗎？是穩定的。
穩定性又是指什么。請查看前一章：基本排序

歸并排序是穩定的，只要 merge() 操作是穩定的，它就是穩定的。

public class Merge
{
 private static void merge(...)
 { /* as before */ }

 private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
 {
     if (hi <= lo) return;
     int mid = lo + (hi - lo) / 2;
     sort(a, aux, lo, mid);
     sort(a, aux, mid+1, hi);
     //這個操作是穩定的
     merge(a, aux, lo, mid, hi);
 }
 public static void sort(Comparable[] a)
 { /* as before */ }
}

這些操作是否穩定取決于我們的代碼怎么寫。在我們的代碼中，

private static void merge(...)
{
 for (int k = lo; k <= hi; k++)
 aux[k] = a[k];
 int i = lo, j = mid+1;
 for (int k = lo; k <= hi; k++)
 {
     if (i > mid) a[k] = aux[j++];
     else if (j > hi) a[k] = aux[i++];
     else if (less(aux[j], aux[i])) a[k] = aux[j++];
     // 如果兩個鍵是相等(或左邊子數組的值小),將輔助數組左邊的值放到原數組中
     else a[k] = aux[i++];
 }
} 

如果兩個鍵是相等的，它取來自左邊子數組的值，那么這意味著如果有兩組相等的鍵，它將總是保留它們的相對順序，先左再右，這就足夠表示歸并操作是穩定的了，因此歸并排序是穩定的。穩定性是排序算法中一個重要的性質。歸并算法不僅高效而且也是穩定的。

這是一種簡單，沒有遞歸的，歸并排序的實現方法

接下來，我們將看從下往上方式的歸并排序。
歸并排序作為遞歸程序是簡單易理解的。雖然這個從下往上的方式不是遞歸，但也比較容易理解。
其基本方法為：

把開始未排序的每一個元素視為已排序的序列，該序列長度為 1

接下來此方法將遍歷并合并 1 對長度為 1 的子序列，成為一組長度為二的子序列

然后對長度為 2 的子序列進行合并再排序，這樣我們就有一組長度為 4 的已排序的子序列

然后合并長度為 8 以此類推

從這個例子中我們可以看出，從長度為 1 的子序列開始，合并排序成長度為 2 的子序列 E-M，然后不斷重復這一過程，直到我們從 16 個長度為 1 的子序列變為兩組長度為八的子序列

在第二輪中，我們將 E-M 與另一組 G-R 合并排序為E-G-M-R，以及 E-S 與 O-R 合并為 E-O-R-S，以此類推，我們有四組長度為四的子序列

第三輪我們將每兩組合并，得到兩組長度為八的子序列，最后一輪的到一個完全排序的序列。

這樣做的好處是這一操作遍歷整個序列并且不需要遞歸。

public class MergeBU
{
 private static void merge(...)
 { /* as before */ }

 public static void sort(Comparable[] a)
 {
     int n = a.length;
     Comparable[] aux = new Comparable[n];
     for (int sz = 1; sz < n; sz = sz+sz)
         for (int lo = 0; lo < n-sz; lo += sz+sz)
             merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1));
     }
}

完整代碼：在此

從以上代碼可以看出它非常容易編寫，

采用同樣的合并代碼并運用嵌套循環(兩個 for 循環)，sz 子序列的大小，第一層循環是 logn 時間復雜度，因為每次我們合并序列為兩倍長，即 sz = sz+sz，直到長度為 n。

然后我們從 low 到 low+size-1 排序

這就是一個完全達到業界標準的排序代碼，相對普通歸并排序，它的唯一負面影響在于需要額外存儲空間，大小與序列長度有關。
除了這點外這是一個很好的歸并排序方法。
以上是從下往上的歸并排序。無論大小，從下往上的歸并排序 時間復雜度為 logN。而每一輪需要進行N次比較，因此總復雜度為 NlogN

學習歸并排序能很好的來幫助理解排序問題自身存在的困難性，現在把這個困難度稱為復雜度，接下來我們將會看關于復雜度的問題。

計算復雜性: 研究解決特定問題 X 的(所有)算法效率的框架.

而為了使其易于理解，我們需要建立所謂的計算模型，即
計算模型： 算法允許執行的操作

對于那種直截了當的排序，我們要做的是建立一個成本模型來計算比較次數。
成本模型： 操作計數。

現在，在問題復雜度的框架內我們只有兩樣東西：
上限： 算法所用開銷/成本的保證，它是由一些(!!)為了解決問題而設計的算法提供。這個上限就表示解決這個問題有多難，我們有個算法可以解決它，并且這是最簡單的。
下限：下限，這是對所有算法的成本/開銷保證的限制。 沒有算法的下限比這個下線做得更好了。
然后我們尋求所謂的最優的算法，就是解決問題“最優的”算法。
最優算法：待解問題的最佳成本保證的算法。也可以說是算法的上限和下限是幾乎相同的(upper bound ~ lower bound),這是解決任何問題的最理想目標

因此，對于排序，讓我們看看這各部分分別是什么。
假設我們訪問數據的唯一方式是通過比較操作，我們所有能使用的只有比較操作，那么一下就是用于分析排序復雜度的框架：

舉例：排序問題

計算復雜性(框架)

計算模型 model of computation：comparison tree (舊版本的講義decision tree)

comparison tree 意味著只能在進行比較的時候訪問數組(e.g., Java Comparable framework)

成本模型 cost model：比較的次數

用 #compares 表示

上界upper bound：~ n lg n from mergesort.

歸并排序提供了一個上界，它是一個保證排序完成的時間與 nlogn 成正比的算法.

下界lower bound：?

最優算法optimal algorithm：?

以下是證明排序下界的基本思想

比方說，我們有3個不同的項，a, b 和 c。不論使用什么算法我們首先要做的是比較三項中的兩項。

分解
比如說，這里是a 和 b。比較之后，有兩種情況 b < c / a < c, 也就是說，它們是有區別的, 在比較中間會有一些代碼，但不管怎樣接下來里有不同的比較。

在這種情況下，如果你從樹的頂部到尾部使用至多三次比較你就可以確定三個不同元素的順序。
用下限的觀點概括就是你需要找到一個最小的比較次數來確定N個元素的順序。

現在，樹的高度，樹的高度，正如我剛剛提到的，是最差情況下比較的次數。
在所有排序中即使是考慮最差情況下的樹，無論輸入是什么，這棵樹告訴我們一個邊界，以及算法的比較次數。

在每一個可能的順序中都至少有一個順序，如果有一個順序沒有出現在針對特定算法的樹中，那么這個算法就不能排序，不能告訴你兩種不同順序中間的差別。

作為命題的下界，使用比較樹來證明任何基于排序算法的比較在最差情況下不得不使用至少 log2(N) 因子的比較次數

并且，通過斯特林近似公式，我們知道 lg(N!) 與 Nlg(N) 成正比。

命題：任何基于比較的排序算法,在最壞的情況下, 必須至少做出 lg（n!）~nlgn 次比較。
證明：

假設數組由 n 個不同的值 a1 到 an 組成

由比較樹的高度h決定最壞情況下排序需要比較的次數

高度為 h 的二叉樹具有 ≤2^h 的葉子

N! 個不同的順序 ? n! 個可到達的葉子

h 是最會情況下，也就是擁有最多葉子的情況下的高度

2^h大于等于葉子節點的數量

葉子節點的數量大于等于N！

這推導出：樹的高度大于等于log2(N!)，根據斯特林公式，那是正比于 NlogN

這就是排序算法復雜度的下限。那么上限的話，根據上邊排序問題的計算復雜性(框架)，已經知道上限是 NlogN, 那意味著歸并排序就是一個最優算法（上限 = 下線）

算法設計的首要目標：嘗試給我們要解決的問題找到最優算法

通過復雜性分析得出的上下文結果：

我們真正證明的是：
歸并排序，就比較的次數而言，是最優的
但是它就空間使用并非最優，歸并排序使用多一倍的額外空間，正比于它要處理的數組的大小。而簡單的算法，比如插入或其他排序，他們根本不適用任何額外的空間。

所以，當我們關注實現并嘗試解決實際問題時，我們把這些理論結果用作一個指導。
在這個例子里，它告訴我們的是：
比如，不要嘗試設計一個排序算法保證大體上比歸并排序，在比較次數上，更好的算法，比方說，1/2NlogN。有方法使用 1/2NlogN次比較的嗎？下限說，沒有；
再比如，也許有一個算法，使用 NlogN 次比較，同時也有最優的空間利用率。不僅在時間上，也在空間上都是最優的。我們即將看到在下面談論這樣的算法。

另一件事是，特定模型下的下限是針對正在研究的特定計算模型得出的，在這個例子中是比較的次數。如果算法有關于鍵值的更多信息，它可能不成立。如果算法可以利用以下優勢，則下限可能不成立：

輸入數組的初始順序

例如：插入排序只需要對部分排序的數組進行線性數量的比較。又或者如果輸入是幾乎排序好的。我們曾看到對于幾乎排序好的文件，插入排序可以是線性時間的。

鍵值的分布

如果有許多相等的鍵，我們可以令它排序得比 NlogN 更快。還有 3-way quicksort 快速排序僅需要在具有恒定數量的不同鍵的數組上進行線性數量的比較。(后續章節)

鍵的表示

例如：基數排序不需要鍵值的比較 - 它們直接通過訪問數據. 通過字符/數位(digit)比較。后續章節）
我們可以利用數字字符的比較，而不是整個鍵的比較，并對特定的實際應用得到一個更快地排序。

計算復雜度是一個非常有用的方法來幫助我們理解算法的性質并幫助指導我們的設計決策。

Q. 以下哪種子數組長度會在對長度為 12 的數組進行歸并排序時出現？
B. { 1, 2, 3, 6, 12 }

對上下界理解的補充
到目前為止，我們一直關注這個問題：“給定一些問題X，我們能否構建一個在大小為n的輸入上運行時間O(f(n))的算法？”
這通常被稱為上限問題，因為我們正在確定問題X的固有難度的上界，我們的目標是使f(n)盡可能小。

下界問題, 這里，目標是證明任何算法必須花費時間 Ω(g(n))時間來解決問題，現在我們的目標讓 g(n)盡可能大。
下限幫助我們理解我們與某個問題的最佳解決方案有多接近：
例如，如果我們有一個在上界時間 O(n log^2 n) 和 下界Ω(n log n) 運行的算法，那么我們的算法有log(n) 的 “差距”：我們希望通過改進算法縮小這個差距。

通常，我們將在限制的計算模型中證明下限，指定可以對輸入執行什么類型的操作以及執行什么開銷。因此，這種模型的下限意味著如果我們想要算法做得更好，我們需要以某種方式在模型之外做一些事情。
今天我們考慮基于比較的排序算法類。這些排序算法僅通過比較一對鍵值對輸入數組進行操作，在比較的基礎上移動元素。