الترتيب بالإدراج (بالإنجليزية: Insertion Sort) هي خوارزمية ترتيب بسيطة مبدأها مشابه لما يستعملهُ أغلب الناس عند ترتيب أوراقهم أو ملفاتهم. وتعمل الخوارزمية بالمرور على البيانات وإدراج كل مدخل في مكانه أولا بأول، ولا تعدّ هذه الطريقة الأفضل بالنسبة للقوائم الكبيرة حيث من يُفضل استخدام خوارزميات متطورة أكثر مثل الترتيب السريع أو الترتيب الدمجي، ولكن للترتيب بالإدراج عدة نقاط إيجابية:
خوارزمية بسيطة: قام عالم الحاسوب جون بنتلي بتطبيق الخوارزمية في ثلاثة سطور بلغة سي ونسخة محسنة في 5 سطور.
أكثر كفاءة للمصفوفات الصغيرة جداً كغيرها من الخوارزمات الرباعية.
كفاءة أعلى عند التطبيق من أغلب خوارزمات الترتيب التربيعية البسيطة مثل الترتيب بالاختيار أو الترتيب بالفقاعات.
متأقلمة الأداء: إذ تتحسن كفاءتها كلما كانت المصفوفة مرتبة أكثر، وينخفض التعقيد الزمني للترتيب إلى O(nk) في مصفوفة لا يبعد أي مدخل أكثر من k خانة عن مكانها المرتب.
الثبات: لا يغير الترتيب النسبي للمدخلات ذات مفاتيح متساوية.
في المكان: يحتاج فقط إلى O(1) ذاكرة اضافية.
فورية: أي أنها تستطيع ترتيب المعلومات أثناء تلقيها بدل الانتظار حتى تلقي المصفوفة الكاملة.
وبرمجياً، تتطلب الخوارزمية عدد مقارنات من الرتبة
n
2
4
{\displaystyle {\frac {n^{2}}{4}}}
، ومعدل تبديلات من الرتبة
n
2
2
{\displaystyle {\frac {n^{2}}{2}}}
، وتعقيد زمني برتبة
O
(
n
2
)
{\displaystyle {\mathcal {O}}(n^{2})}
.