?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Insertion Sort: When to Use

ALGOR-EBVE6E

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.

A

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)$

B

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.

C

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)$

D

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