
Insertion Sort là một thuật toán sắp xếp đơn giản hoạt động bằng cách chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Ban đầu, phần đã sắp xếp chỉ chứa một phần tử (phần tử đầu tiên), sau đó các phần tử từ phần chưa sắp xếp được lấy từng cái một và chèn vào vị trí thích hợp trong phần đã sắp xếp.