ในสาขาว ทยาการคอมพ วเตอร การเร ยงลำด บแบบแทรก อ งกฤษ insertion sort เป นข นตอนว ธ การเร ยงลำด บอย างง าย ทำงานโดยจะแบ งข

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

การเรียงลำดับแบบแทรก
ตัวอย่างการเรียงลำดับแบบแทรกจากข้อมูลสุ่ม
ประเภท	ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล	รายการ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	$O(n^{2})$
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	$O(n)$
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	$O(n^{2})$
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	ใช้พื่นที่ $O(1)$ เพิ่มเติม

ขั้นตอนวิธี (อัลกอริทึม)

ตัวอย่างทีละขั้นตอน

การเรียงลำดับข้อมูลในรายการดังนี้ 3 9 8 7 6 ด้วยขั้นตอนวิธีแบบแทรก เริ่มต้นด้วยข้อมูลทุกตัวยกเว้นตัวแรกยังไม่ได้เรียง ข้อมูลที่อยู่ในเครื่องหมาย (..) ถือว่าเป็นข้อมูลที่เรียงจากน้อยไปมากแล้ว
ครั้งที่ 1
[ (3) 9 8 7 6 ] $\to$ [ (3 9) 8 7 6 ]
ครั้งที่ 2
[ (3 9) 8 7 6 ] $\to$ [ (3 9 8) 7 6 ]
[ (3 9 8) 7 6 ] $\to$ [ (3 8 9) 7 6 ]
ครั้งที่ 3
[ (3 8 9) 7 6 ] $\to$ [ (3 8 9 7) 6 ]
[ (3 8 9 7) 6 ] $\to$ [ (3 8 7 9) 6 ]
[ (3 8 7 9) 6 ] $\to$ [ (3 7 8 9) 6 ]
ครั้งที่ 4
[ (3 7 8 9) 6 ] $\to$ [ (3 7 8 9 6) ]
[ (3 7 8 9 6) ] $\to$ [ (3 7 8 6 9) ]
[ (3 7 8 6 9) ] $\to$ [ (3 7 6 8 9) ]
[ (3 7 6 8 9) ] $\to$ [ (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