الفرز بالإدراج

يبني جزءًا مرتّبًا على اليسار، قيمة بعد قيمة. تُخرَج كل قيمة جديدة وتُنقل يسارًا حتى تصل إلى قيمة أصغر منها.

• الأفضل Ω(n)
• المتوسط Θ(n²)
• الأسوأ O(n²)
• الذاكرة O(1)
• مستقر
• بلا ذاكرة إضافية

ماذا تعني هذه المصطلحات؟

• الأفضل: كيف يزداد الوقت مع حجم القائمة n عندما تكون المدخلات هي الأسهل لهذه الخوارزمية.
• المتوسط: النمو المعتاد للوقت مع n. في n² إذا تضاعف عدد القيم صار الوقت نحو أربعة أضعاف، أما n log n فينمو أبطأ بكثير.
• الأسوأ: نمو الوقت مع أصعب المدخلات. مفيد عندما يجب ألا تنخفض السرعة أبدًا.
• الذاكرة: كم يحتاج من ذاكرة إضافية غير القائمة. 1 يعني بضعة متغيرات، و n يعني نسخة من القائمة.
• مستقر: تحافظ القيمتان المتساويتان على ترتيبهما الأصلي. يهم هذا عند الفرز حسب حقل واحد من السجل.
• بلا ذاكرة إضافية: يرتّب داخل القائمة نفسها، دون قائمة ثانية.