Can you summarize the following document?
        
  最早擁有排序概念的機器出現在1901至1904年間由赫爾曼·何樂禮發明出使用基數排序法的分類機,此機器系統包括打孔,製表等功能,1908年分類機第一次應用於人口普查,並且在兩年內完成了所有的普查資料和歸檔。 赫爾曼·何樂禮在1896年創立的分類機公司的前身,為電腦製表記錄公司(CTR)。他在電腦製表記錄公司曾擔任顧問工程師,直到1921年退休,而電腦製表記錄公司在1924年正式改名為IBM。

  Insertion Sort 和打撲克牌時,從牌桌上逐一拿起撲克牌,在手上排序的過程相同。  舉例:  Input: {5 2 4 6 1 3}。  首先拿起第一張牌, 手上有 {5}。  拿起第二張牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。  拿起第三張牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。  以此類推。

  一般來說,插入排序都採用in-place在陣列上實現。具體演算法描述如下:  可以採用二分查詢法來減少“比較操作”的數目,而由於“交換操作”的數目不變,演算法的時間複雜度依舊為formula_2 。該演算法可以認為是插入排序的一個變種,稱為二分查詢插入排序。

  此範例程式以C語言實現。  此範例程式以Objective C實現。

  如果目標是把n個元素的序列升序排列,那麼採用插入排序存在最好情況和最壞情況。最好情況就是,序列已經是升序排列了,在這種情況下,需要進行的比較操作需formula_3次即可。最壞情況就是,序列是降序排列,那麼此時需要進行的比較共有formula_4次。插入排序的賦值操作是比較操作的次數減去formula_3次,(因為formula_3次迴圈中,每一次迴圈的比較都比賦值多一個,多在最後那一次比較並不帶來賦值)。平均來說插入排序演算法複雜度為formula_7。因而,插入排序不適合對於資料量比較大的排序應用。但是,如果需要排序的資料量很小,例如,量級小於千;或者若已知輸入元素大致上按照順序排列,那麼插入排序還是一個不錯的選擇。 插入排序在工業級庫中也有著廣泛的應用,在STL的sort演算法和stdlib的qsort演算法中,都將插入排序作為快速排序的補充,用於少量元素的排序(通常為8個或以下)。
插入排序(英語:Insertion Sort)是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列,對於未排序資料,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常採用in-place排序(即只需用到formula_1的額外空間的排序),因而在從後向前掃描過程中,需要反覆把已排序元素逐步向後挪位,為最新元素提供插入空間。