Insertion sort

với giải thuật này, ta xem 1 mảng với 1 phần tử a[0] như là một mảng đã sắp xếp (có thứ tự).
1. Bước 1 ta chèn phần tử a[1] vào mảng có thứ tự a[0], sao cho nó trở thành mảng có thứ tự.
2. Bước 2 ta chèn phần tử a[2] vào mảng có thứ tự a[1], a[0] sao cho nó trở thành mảng có thứ tự.
3. Tổng quát: Ở bước thứ i, ta chèn phân tử a[i] vào mảng có thứ tự a[i -1], a[i -2], ..., a[0] để được mảng có thứ tự.
Ta thấy rằng a[i] sẽ được xen vào vị trí thích hợp trong mảng a[i-1],..,a[0]. Chúng ta so sánh: a[i], a[i-1] ...

Code:

public static void sort(int[] array) {

        for (int i = 1; i < array.length; i++) {
            int index = i;
            while (index > 0 && array[index - 1] < array[index]) {
                // swap
                int temp = array[index];
                array[index] = array[index - 1];
                array[index - 1] = temp;
                index--;
            }
        }
    }