Insertion Sort เป็นอัลกอริทึมอย่างง่ายอัลกอริทึมหนึ่งสำหรับการจัดเรียงค่า อัลกอริทึมมีการทำงานเป็นรอบที่ประกอบด้วยจำนวนรอบ N – 1 รอบ (passes) สำหรับจากรอบที่ p = 2 ถึง N ก็จะประกันได้ว่าสมาชิกที่อยู่ในตำแหน่ง 1 ถึง p จะถูกจัดอยู่ในลำดับที่ถูกต้องแล้ว การทำงานของ Insertion sort จะใช้ประโยชน์จากความจริงที่ว่าการทำงานในรอบที่ p นั้นสมาชิกในตำแหน่งที่ 1 ถึง p - 1 เป็นสมาชิกที่ถูกจัดเรียงเรียบร้อยแล้ว รูปที่ 7.1 แสดงตัวอย่างข้อมูลหลังการทำงานแต่ละรอบของ insertion sort
รูปที่ 7.1 แสดงวิธีทั่วไปของอัลกอริทึมโดยการทำงานในรอบที่ p เราจะเคลื่อนสมาชิกของตำแหน่ง p ไปทางซ้ายจนพบตำแหน่งที่ถูกต้องในระหว่างกลุ่มสมาชิก p + 1 ตัวแรก รูปที่ 7.2 แสดงโปรแกรมที่ทำงานตามที่ได้กล่าวมานี้ บรรทัดที่ 2 ถึง 5 จะทำการเลื่อนสมาชิกแบบที่กล่าวมาโดยไม่ได้มีการสลับค่ากันกับสมาชิกอื่น ๆ สมาชิกตัวที่ p ถูกจัดเก็บในตัวแปร tmp และสมาชิกที่มีตำแหน่งอยู่ข้างหน้าและมีค่ามากกว่ามันก็จะถูกเลื่อนไปทางขวามือ 1 ตำแหน่งเพื่อจะได้ช่องว่างในตำแหน่งสำหรับวางค่าของ tmp ลงในตำแหน่งนั้น
| เริ่มต้น | 34 | 8 | 64 | 51 | 32 | 21 | จำนวนตำแหน่งที่เลื่อน |
| หลังจาก p = 1 | 8 | 34 | 64 | 51 | 32 | 21 | 1 |
| หลังจาก p = 2 | 8 | 34 | 64 | 51 | 32 | 21 | 0 |
| หลังจาก p = 3 | 8 | 34 | 51 | 64 | 32 | 21 | 1 |
| หลังจาก p = 4 | 8 | 32 | 34 | 51 | 64 | 21 | 3 |
| หลังจาก p = 5 | 8 | 21 | 32 | 34 | 51 | 64 | 4 |
รูปที่ 7.1 ข้อมูลหลังการทำงานแต่ละรอบของ insertion sort
public static void insertionSort( Comparable [ ] a ) { int j; /* 1*/ for( int p = 1; p < a.length; p++ ) { /* 2*/ Comparable tmp = a[ p ]; /* 3*/ for ( j = p; j > 0 && tmp.compareTo(a[ j - 1 ]) < 0; j-- ) /* 4*/ a[ j ] = a[ j - 1 ]; /* 5*/ a[ j ] = tmp; } }
รูปที่ 7.2 โปรแกรมฟังก์ชัน Insertion sort
เนื่องจากโปรแกรมใช้ลูปซ้อน และแต่ละลูปอาจทำงานได้เป็นจำนวน N รอบ ดังนั้น insertion sort จึงเป็น $O(N^2)$ และ running time นี้เป็นขอบเขตที่มั่นคง เนื่องจากถึงแม้อินพุตจะมีลำดับที่เรียงกลับกันก็จะยังได้ running time นี้ หากพิจารณาอย่างละเอียดจะพบว่าในบรรทัดที่ 3 จะมีการทดสอบค่าที่มีจำนวนครั้งทำมากที่สุด p+1 ครั้งสำหรับแต่ละค่า p ดังนั้นเมื่อรวมทุกค่า p เข้าด้วยกันจะได้ $∑_{i=2}^N i=2+3+4+⋯+N=\Theta(N^2 )$
อีกด้านหนึ่ง ถ้าอินพุตมีการจัดเรียงไว้เรียบร้อยแล้วแต่แรก อัลกอริทึมนี้ก็จะมี running time เป็น $O(N)$ เนื่องจากว่าคำสั่งที่เป็นการทดสอบในลูป for ด้านใน (inner loop) จะล้มเหลวในทันที ความจริงแล้วถ้าข้อมูลที่เป็นอินพุตเกือบทั้งหมดได้รับการจัดเรียงมาก่อนแล้ว insertion sort ก็จะทำงานได้เร็วมาก เนื่องจากความหลากหลายของข้อมูลอินพุตเองทำให้การวิเคราะห์กรณีเฉลี่ยได้ประโยชน์มากกว่า และสำหรับกรณีเฉลี่ยแล้วอัลกอริทึมนี้จะมี running time เป็น $\Theta(N^2)$ ซึ่งจะกล่าวถึงต่อไป