When inserting a new element into a sorted array, what must be done to maintain the sorted order?

Đáp án đúng: "Shift elements after the insertion point to create space". Mảng chiếm một dải ô nhớ liền kề nên không có chỗ trống sẵn ở giữa; muốn chèn mà vẫn giữ thứ tự, ta tìm vị trí đúng rồi dịch mọi phần tử từ vị trí đó về sau sang phải một ô, bắt đầu dịch từ phần tử cuối để không ghi đè, sau đó đặt giá trị mới vào ô vừa trống. Phương án "Shift all elements to the left to create space at the beginning" không tạo được chỗ trống mà còn ghi đè phần tử đầu làm mất dữ liệu, và chỉ phục vụ việc chèn vào đầu. Phương án "Replace the last element with the new element" vừa xoá mất phần tử cuối vừa phá vỡ thứ tự nếu giá trị mới không phải lớn nhất. Phương án "Reorganize the array into a linked list structure" đổi hẳn kiểu cấu trúc dữ liệu, không phải việc cần làm để chèn.