51. A k-sorted array is a nearly sorted array in which no element is more than k locations away from its final
position in the sorted array. Thus, a 0-sorted array is completely sorted and every array of size n is n-sorted.
Suppose that A is a k-sorted array of size n. If insertion sort is used to sort A, what is the order of growth
of the number of comparisons performed by the sorting algorithm in the worst case?
(A) Theta k (B) Theta kn (C) Theta k^2n (D) Theta n logk n (E) Theta n^2
