(4%) (c) Can you use recursion to solve the same problem? Explain.

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).

題組內容

(4%) (c) Can you use recursion to solve the same problem? Explain.

相關申論題

相關試卷