Insertion Sort menyisipkan setiap elemen ke posisi yang benar, seperti menyusun kartu di tangan.

Kompleksitas: O(n²) worst case, O(n) best case (data hampir terurut)

Cara kerja:

1. Ambil elemen berikutnya
2. Bandingkan mundur dengan elemen sebelumnya
3. Geser elemen yang lebih besar ke kanan
4. Sisipkan di posisi yang tepat

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const current = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // Geser ke kanan
      j--;
    }
    arr[j + 1] = current; // Sisipkan
  }
  return arr;
}

insertionSort([5, 2, 4, 6, 1, 3]);
// [5, 2, 4, 6, 1, 3] → ambil 2, sisip → [2, 5, 4, 6, 1, 3]
// [2, 5, 4, 6, 1, 3] → ambil 4, sisip → [2, 4, 5, 6, 1, 3]
// [2, 4, 5, 6, 1, 3] → ambil 6, sudah benar
// [2, 4, 5, 6, 1, 3] → ambil 1, sisip → [1, 2, 4, 5, 6, 3]
// [1, 2, 4, 5, 6, 3] → ambil 3, sisip → [1, 2, 3, 4, 5, 6]

Kelebihan:

• Cepat untuk data hampir terurut — O(n) best case
• Stabil
• In-place — O(1) memori tambahan
• Bagus untuk dataset kecil (< 50 elemen)

Fun fact: JavaScript Array.sort() di V8 menggunakan TimSort yang menggabungkan Merge Sort + Insertion Sort (untuk sub-array kecil).

🎭 Analogi sehari-hari: Susun kartu remi yang kamu pegang. Setiap kartu baru yang ambil dari deck, sisipkan ke posisi yang tepat di tangan. Kartu yang lebih besar geser ke kanan. Itu insertion sort — persis seperti orang main kartu beneran.

💡 Mengapa Insertion Sort dipakai dalam TimSort dan Quicksort? Untuk sub-array kecil (<10 elemen), insertion sort lebih cepat dari merge/quick karena konstanta lebih kecil dan cache friendly. Algoritma sort hybrid (TimSort, IntroSort) fallback ke insertion sort saat partition kecil.

⚠️ Jebakan umum:

• Pakai untuk data besar acak = O(n²) lambat
• Lupa start dari i=1 — i=0 gak ada yang sebelumnya untuk dibandingkan
• Salah arah perbandingan untuk descending = data malah jadi ascending
• Pakai swap bukan shift = lebih lambat (extra assignment)

🎯 Insertion Sort sangat cocok untuk:

• Hampir sorted data → O(n) best case (cuma cek tetangga, gak shift)
• Streaming data — sort online saat data datang satu per satu
• Sub-array kecil dalam algoritma sort hybrid
• Linked list sorted insert — sisip ke posisi tepat O(n)

🧪 Tebakan cepat: Data hampir sorted (cuma 5 elemen out-of-place dari 1 juta). Insertion: ~O(n) = 1jt. Merge sort: O(n log n) = 20jt. Insertion 20x lebih cepat untuk hampir-sorted!

TL;DR: Insertion Sort = sisip elemen ke posisi tepat di prefix sorted. O(n²) worst, O(n) best (hampir sorted). Default untuk data kecil dan hampir-sorted.