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.