Final answer:
The running time of insertion sort on a randomly ordered array with only three different element values is in between linear and quadratic. It can perform better than quadratic time but not as good as linear due to the likelihood of elements being equal.
Step-by-step explanation:
If we use insertion sort on a randomly ordered array where elements have only one of three values, the running time is in between linear and quadratic. This is because, in the best-case scenario (where the array is already sorted or nearly sorted), insertion sort runs in linear time (O(n)). However, in the worst-case scenario (where the array is in reverse order), it runs in quadratic time (O(n²)). In this specific case where there are only three different values, the sort can perform faster than the worst-case scenario due to the high likelihood of elements being equal, which can reduce the number of necessary swaps. Thus, while not strictly linear, the running time would often be closer to linear than to the quadratic, making the answer 'c) In between'.