void insertion_sort(){

              int i, j, k, temp;

              for (i = 1; i< N; i++){

                      temp = a[i];

                   j=i-1;

              while ((a[j] > temp)&&(j>=0)) {

                      a[j+1]=a[j];

                    j--;

                }

               a[j+1]=temp;

            }

       }

   Ñeå cheøn phaàn töû thöù K+1 vaøo K phaàn töû ñaàu daõy ñaõ coù thöù töï chuùng ta seõ tieán haønh tìm vò trí ñuùng cuûa phaàn töû K+1 trong K phaàn töû ñaàu baèng caùch vaän duïng thuaät giaûi tìm kieám tuaàn töï (Sequential Search).

    Sau khi tìm ñöôïc vò trí cheøn (chaéc chaén coù vò trí cheøn) thì chuùng ta seõ tieán haønh cheøn phaàn töû K+1 vaøo ñuùng vò trí cheøn baèng caùch dôøi caùc phaàn töû töø vò trí cheøn ñeán phaàn töû thöù K sang phaûi (ra phía sau) 01 vò trí vaø cheøn phaàn töû K+1 vaøo vò trí cuûa noù.

   Thuật toán sử dụng 2 vòng lặp. Vòng lặp ngoài duyệt khoảng N lần, và vòng lặp trong duyệt trung bình N/4 lần (giả sử duyệt đến giữa nửa đã sắp thì gặp vị trí cần chèn). Do đó, độ phức tạp trung bình của thuật toán là O(N2/4) = O(N2).