Can you summarize the following document?
        
  希爾排序按其設計者希爾(Donald Shell)的名字命名,該演算法由1959年公佈。一些老版本教科書和參考手冊把該演算法命名為Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根據Metzner本人的說法,“我沒有為這種演算法做任何事,我的名字不應該出現在演算法的名字中。”

  原始的演算法實現在最壞的情況下需要進行O("n")的比較和交換。 V. Pratt的書對演算法進行了少量修改,可以使得效能提升至O("n" log "n")。這比最好的比較演算法的O("n" log "n")要差一些。  希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的效能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序,演算法的最後一步就是普通的插入排序,但是到了這步,需排序的資料幾乎是已排好的了(此時插入排序較快)。  假設有一個很小的資料在一個已按升序排好序的陣列的末端。如果用複雜度為O("n")的排序(氣泡排序或插入排序),可能會進行"n"次的比較和交換才能將該資料移至正確位置。而希爾排序會用較大的步長移動資料,所以小資料只需進行少數比較和交換即可到正確位置。  一個更好理解的希爾排序實現:將陣列列在一個表中並對列排序(用插入排序)。重複這過程,不過每次用更長的列來進行。最後整個表就只有一列了。將陣列轉換至表是為了更好地理解這演算法,演算法本身僅僅對原陣列進行排序(通過增加索引的步長,例如是用codice_1而不是codice_2)。  例如,假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我們以步長為5開始進行排序,我們可以通過將這列表放在有5 zh-hans:列; zh-hant:行;的表中來更好地描述演算法,這樣他們就應該看起來是這樣: 然後我們對每列進行排序:  將上述四行數字,依序接在一起時我們得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了,然後再以3為步長進行排序:  排序之後變為:  最後以1步長進行排序(此時就是簡單的插入排序了)。

  步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。演算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序,最終演算法以步長為1進行排序。當步長為1時,演算法變為普通插入排序,這就保證了資料一定會被排序。  Donald Shell最初建議步長選擇為formula_1並且對步長取半直到步長達到1。雖然這樣取可以比formula_2類的演算法(插入排序)更好,但這樣仍然有減少平均時間和最差時間的餘地。  已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109...),該序列的項來自formula_3和formula_4這兩個算式/lydia.sinapova/www/cmsc250/LN250_Weiss/L12-ShellSort.htm#increments。這項研究也表明“比較在希爾排序中是最主要的操作,而不是交換。”用這樣步長序列的希爾排序比插入排序要快,甚至在小陣列中比快速排序和堆排序還快,但是在涉及大量資料時希爾排序還是比快速排序慢。  另一個在大陣列中表現優異的步長序列是(斐波那契數列除去0和1將剩餘的數以黃金分割比的兩倍的冪進行運算得到的數列):(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,...)
希爾排序(Shellsort),也稱遞減增量排序演算法,是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。