การเรียงลำดับแบบแทรก

ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบแทรก () เป็นขั้นตอนวิธีการเรียงลำดับอย่างง่าย ทำงานโดยจะแบ่งข้อมูลในรายการเป็นสองส่วนคือส่วนที่เรียงแล้วและส่วนที่ยังไม่เรียง แน่นอนว่าในตอนเริ่มแรกส่วนที่เรียงแล้วก็จะมีอย่างน้อยหนึ่งตัว และจะเริ่มหยิบข้อมูลตัวหนึ่งของส่วนที่ยังไม่เรียงมาเปรียบเทียบเพื่อหาตำแหน่งที่เหมาะสมในการแทรกลงในข้อมูลส่วนที่เรียงแล้ว ลักษณะเดียวกับการเรียงไพ่ในมือ และด้วยประสิทธิภาพ O(n2)  ดังนั้นการเรียงลำดับแบบแทรกจึงไม่เหมาะในการทำงานในรายการที่มีจำนวนสมาชิกมาก ๆ ซึ่งขั้นตอนวิธีการเรียงลำดับซึ่งซับซ้อนกว่าเช่น การเรียงลำดับแบบเร็ว, การเรียงลำดับแบบผสาน, การเรียงลำดับแบบฮีป มีความเหมาะสมมากกว่า

 ขั้นตอนวิธี (อัลกอริทึม) 
 ตัวอย่างทีละขั้นตอน 
การเรียงลำดับข้อมูลในรายการดังนี้ 3 9 8  7 6 ด้วยขั้นตอนวิธีแบบแทรก เริ่มต้นด้วยข้อมูลทุกตัวยกเว้นตัวแรกยังไม่ได้เรียง ข้อมูลที่อยู่ในเครื่องหมาย (..) ถือว่าเป็นข้อมูลที่เรียงจากน้อยไปมากแล้ว

ครั้งที่ 1

[ (3) 9 8 7 6 ]  [ (3 9) 8 7 6 ]

ครั้งที่ 2

[ (3 9) 8 7 6 ]  [ (3 9 8) 7 6 ]

[ (3 9 8) 7 6 ]  [ (3 8 9) 7 6 ]

ครั้งที่ 3

[ (3 8 9) 7 6 ]  [ (3 8 9 7) 6 ]

[ (3 8 9 7) 6 ]  [ (3 8 7 9) 6 ]

[ (3 8 7 9) 6 ]  [ (3 7 8 9) 6 ]

ครั้งที่ 4

[ (3 7 8 9) 6 ]  [ (3 7 8 9 6) ]

[ (3 7 8 9 6) ]  [ (3 7 8 6 9) ]

[ (3 7 8 6 9) ]  [ (3 7 6 8 9) ]

[ (3 7 6 8 9) ]  [ (3 6 7 8 9) ]

เรียงเสร็จเรียบร้อย

 ตัวอย่างรหัสเทียม 
begin insertionSort ( A : list of sortable items )
   for i = 1 to length (A) - 1
      item = A[i]
      cmpPos = i - 1
      while cmpPos >= 0 and item < A[cmpPos]
         A[cmpPos + 1] = A[cmpPos]
         cmpPos = cmpPos - 1
      end while
      A[cmpPos + 1] = item
   end for
end

หมวดหมู่:ขั้นตอนวิธีการเรียงลำดับ
หมวดหมู่:การเรียงแบบเปรียบเทียบ
หมวดหมู่:การเรียงแบบเสถียร
หมวดหมู่:การเรียงแบบออนไลน์