Ý tưởng
Xét dãy a1, a2…., an, trong đó i-1 phần tử đầu tiên a1, a2,…,an đã có thứ tự. Tìm vị trí thích hợp để chèn phần tử ai vào vị trí thích hợp trong i-1 phần tử đã sắp để có dãy mới a1, a2,…,ai trở nên có thứ tự. Vị trí này nằm giữa ak-1 và ak thỏa ak-1 ≤ ai < ak (1 ≤ k < i).
Giải thuật
Bước 1: i = 2 // Giả sử có đoạn a[1] đã được sắp
Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào.
Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i].
Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp
Bước 5: i = i +1;
Nếu i ≤ n : lặp lại bước 2.
Ngược lại: Dừng
BINSERTION SORT
BInsertion Sort cũng tương tự như Insertion Sort, chỉ khác ở cách tìm vị trí thích hợp pos trong đoạn a[0] đến a[i-1]. Do đoạn a[0] đến a[i-1] đã có thứ tự nên ta có thể sử dụng giải thuật tìm nhị phân (Binary Search) để thực hiện việc tìm vị trí pos.
Đó là ý tưởng của BInsertion Sort – giải thuật sắp xếp chèn nhị phân.