3. Consider Shell sort where we apply insertion sort to k subarrays (or columns) for k = 3 and k = 2. For a particular k, we say that the array

is k-sorted if each of the k subarrays, as obtained/defined in the context of Shell sort, is sorted properly. The 1-th subarray, with 0≤1≤k-1, contains the elements A[1], A[1+k], ... assuming that A is the unsorted array, and the starting index is 0. Consider k = 3 and k =2. Shell sort will sort the array by first applying insertion sort to k = 3 subarrays, followed by applying insertion sort to k = 2 subarrays. It turns out that the resulted 2- sorted array is still 3-sorted. In other words, if we subdivide the 2-sorted array into k = 3 subarrays (according to the definition of subarrays in the context of Shell sort), each of the k = 3 subarrays is still sorted. Justify that now, each element in the array is at most one position off its correct position. (Hint: Consider an element at position i in an array that has been 3-sorted and 2-sorted. What can you say about the relation between this element and the element at position i+2, i+3, i +4, ...?) (Now, a more challenging problem: argue that after applying insertion sort to k = 3 subarrays and then to k = 2 subarrays, the array is both 3-sorted and 2-sorted. This challenge problem is not part of this homework.)