鏈式歸并排序法

摘要：介紹一種鏈式存儲的逐步歸并排序算法，其最佳時間復雜度為O(n)，空間復雜度為O(1)。

關鍵詞：鏈表；歸并排序；算法；復雜性

0 引言

排序問題是指給定一個數據項集，使其中的數據按遞增或遞減排列。數據項可以是具有線性順序的任意對象。排序是計算機科學中最重要的研究課題之一，據統計，在大型計算中心，排序工作往往要占去大約1/4的計算時間。排序具有極高的理論和實際價值，2000年被列為對科學和工程計算的研究與實踐影響最大的十大問題之一。對排序算法的研究無論是在理論上還是在實踐上都具有重大的意義。

數十年來，人們在此問題上進行了不懈的研究，獲得了大量的研究成果，各種排序方法有近百種之多。這其中最常用的就有：快速排序、希爾排序、冒泡排序、插入排序、選擇排序、堆排序、歸并排序、基數排序、雜湊排序等十多種排序算法。這些排序算法基本上可以歸為兩大類：基于比較的排序和不基于比較的排序。基于比較的排序是指要將各個數據項進行直接或間接的比較以確定每個數據的最終位置。理論研究表明，不基于比較的排序如基數排序、雜湊排序的時間復雜度可以達到O(n)，但問題是這類排序一般都需要較大的輔助空間，而且對數據項有著比較嚴格的要求，只能在特性場合下使用。基于比較的排序的時間下限是O(nlog2n)，快速排序、堆排序、歸并排序的平均時間復雜度都可以達到這個級別。這類排序對數據項沒有任何限制，因而獲得了更為廣泛的應用。……