Limited access

Upgrade to access all content for this subject

Insertion sort is a simple and intuitive algorithm but has a worst-case runtime of $\mathcal{O}(n^2)$. However, sometimes it may be preferable to use this algorithm.

Which of the following statements about insertion sort are true?

Select ALL that apply.


If a list of size $n$ is $k$-sorted, meaning each element in the unsorted list is at most $k$ away from its index in the sorted list, then the expected runtime of insertion sort is $\mathcal{O}(n k)$


An insertion sort may be preferable to a recursive sort such as merge sort or quick sort due to the overhead of making the recursive calls.


If a list of size $n$ contains k unique elements where $k \ll n$, insertion sort has a worst-case run-time of $\mathcal{O}(n k)$


If a list of size $n$ is completely sorted, insertion sort has sub-linear runtime.

Select an assignment template