Tư tưởng của thuật toán là i, j để chỉ vị trí, ví dụ j=2 tức là vị trí thứ 2
INSERTION-SORT.A/
for j = 2 to A:length
     key = A[j]
     // Insert A[j] into the sorted sequence A[1.. j - 1].
     i = j - 1
     while i > 0 and A[i] > key
           A[i + 1] = A[i]
           i = i - 1
     A[i + 1] = key

Cách thực hiện như sau

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) { 
        key = arr[i]; 
        j = i - 1; 
  
        /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
}