Time and Space Complexity

Zaman Karmaşıklığı:

• En İyi Durum: O(n)
  • Dizi zaten sıralı olduğunda, Insertion Sort sıralı düzeni onaylamak için yalnızca bir geçiş yapar.
• Ortalama ve En Kötü Durum: O(n²)
  • Ortalama ve en kötü durumlarda, her bir öğe için sıralanmış kısmın tamamı boyunca karşılaştırma ve kaydırma yapmamız gerekebileceğinden karesel zaman alır.

Alan Karmaşıklığı:

• O(1)
  • Insertion Sort "yerinde" (in-place) bir algoritmadır, yani girdi boyutuyla orantılı ek bellek gerektirmez.
  • Sıralama için kullanılan alan, girdi boyutundan bağımsız olarak sabit kalır.

Özet:

• Insertion Sort, küçük veri kümeleri veya neredeyse sıralanmış diziler için verimlidir.
• Karesel zaman karmaşıklığı nedeniyle büyük veri kümeleri için daha az uygundur.
• Alan karmaşıklığı sabittir, bu da onu her türlü girdi boyutu için bellek açısından verimli kılar.