Sorting costs work, but makes later queries easier

Sorting is preparation. Once a mark list is sorted, endpoints give extrema and positions help select high or low values. A descending list makes the first k entries easy to read; an ascending list puts the largest entries at the end. Handle empty inputs and k larger than the list length explicitly.

“Top k entries” and “top k DISTINCT mark levels” differ. The first three descending Maths marks are 97,97,93; the first three distinct levels are 97,93,89. To collect every student at those levels, continue across ties and do not stop after three records.

In this copying insertion implementation, each new call copies every element already accumulated. Sorting n items copies 0+1+…+(n−1) old elements: n(n−1)/2, which is 435 for 30. The inserted flag can reduce KEY COMPARISONS after placement, but it does not avoid copying the remainder.

Other insertion-sort implementations have different best-case costs and may shift elements rather than build new lists. The tutorial does not justify calling every version equally fast. Faster large-scale sorting algorithms exist; this week focuses on a clear correct method and on reusing its output.