申論題

10. (10%) The shell sort algorithm is an improved version of the straight insertion sort. In the shell sort, a list of N elements is divided into K segments, where K is known as the increment. For example, in Figure 3, K is 3. The first, fourth, seventh, and tenth elements make up segment 1. For each pass, the data in each segment are sorted in Insertion Sort. Thus, after insertion sort, there are three different ordered lists. After each pass through the data, the increment is divided by two (K/2) until, in the final pass, it is 1. Please prove (explain) the time complexity of Shell sort is close to O(N log N).