Flowchart Insertion sort

Definisi
    Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

Macam- macam metode insertion sort

1. Langsung (Straight Insertion Sort)
Ilustrasi dari langkah-langkah pengurutan dengan algoritma penyisipan langsung (straight insertion sort) dapat dilihat pada tabel

2. Metode Penyisipan Biner (Binary Insertion Sort)
Metode pengurutan dengan algoritma penyisipan biner (binary insertion sort) memperbaiki metode pengurutan dengan algoritma penyisipan langsung dengan melakukan proses perbandingan yang lebih sedikit sehingga proses pengurutan lebih cepat.
Metode penyisipan biner melakukan proses perbandingan dengan membagi dua bagian data dari posisi 0 sampai dengan i-1 yang disebut dengan bagian kiri dan kanan. Apabila data pada posisi ke i berada pada jangkauan kiri maka proses perbandingan dilakukan hanya pada bagian kiri dan menggeser posisi sampai i.

              Kelebihan dan kekurangan insertion sort
-  Kelebihan
1.Sederhana dalam penerapannya.
2.Mangkus dalam data yang kecil
3.Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.
4.Mangkus dalam data yang sebagian sudah terurut.
5.Lebih mangkus dibanding Bubble Sort dan Selection Sort.
6.Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.
7.Stabil.

-  Kekurangan
a.Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
b.Untuk larik yang jumlahnya besar ini tidak praktis.
c.Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
d.Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.