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: 17, 5, 3, 11, 10, 8, 13, 4, 8, 6 What is the list after the FIRST TWO steps of insertion sort? (sorting from smallest to largest).

Đáp án đúng: "3, 5, 17, 11, 10, 8, 13, 4, 8, 6". Insertion sort chỉ sắp dần đoạn đầu, phần sau chưa bị chạm tới. Bước i = 1 chèn 5 vào đoạn chỉ gồm 17, được 5, 17, 3, 11, 10, 8, 13, 4, 8, 6. Bước i = 2 chèn 3 vào đoạn 5, 17, đẩy cả hai sang phải, được 3, 5, 17, 11, 10, 8, 13, 4, 8, 6; ba ô đầu đã sắp, bảy ô sau giữ nguyên thứ tự ban đầu. Dãy "3, 5, 11, 10, 8, 13, 4, 8, 6, 17" đẩy 17 xuống 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. Dãy "3, 4, 17, 11, 10, 8, 13, 5, 8, 6" hoán vị 4 với 5, 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 "3, 4, 5, 11, 10, 8, 13, 17, 8, 6" đã sắp xong ba giá trị nhỏ nhất của cả mảng, vượt xa hai bước đầu.