The following is the main part of insertion sort pseudocode: for i := 1 to n-1 insert a[i] into sorted sublist {a[0],...,a[i-1]} so that the sortedness is still kept. end for Select the most correct solution: Consider the list of ten integers below: 16, 4, 2, 11, 9, 7, 12, 3, 7, 5 What is the list after the FIRST TWO steps of insertion sort? (sorting from smallest to largest).

Đáp án đúng: "2, 4, 16, 11, 9, 7, 12, 3, 7, 5". Insertion sort chỉ làm việc trong đoạn đầu đã sắp, phần sau giữ nguyên vị trí ban đầu. Bước i = 1 chèn 4 vào đoạn đã sắp chỉ gồm 16, được 4, 16, 2, 11, 9, 7, 12, 3, 7, 5. Bước i = 2 chèn 2 vào đoạn 4, 16, đẩy cả hai sang phải, được 2, 4, 16, 11, 9, 7, 12, 3, 7, 5; ba ô đầu đã sắp còn bảy ô sau chưa bị chạm tới. Dãy "2, 3, 4, 11, 9, 7, 12, 16, 7, 5" đã lôi số 3 từ ô thứ tám về đầu, việc chỉ xảy ra ở bước i = 7. Dãy "2, 3, 16, 11, 9, 7, 12, 4, 7, 5" hoán vị 3 với 4, tức chọn phần tử nhỏ nhất toàn mảng rồi đổi chỗ, đó là lối của selection sort. Dãy "2, 4, 11, 9, 7, 12, 3, 7, 5, 16" đẩy 16 về cuối mảng, dấu vết của một lượt bubble sort, còn phép chèn không bao giờ đưa phần tử ra khỏi đoạn đã sắp.