Shell Sort
Shell Sort is a generalization of Insertion Sort to arrange a list of nn elements A.
1 insertionSort(A, n, g)
2 for i = g to n-1
3 v = A[i]
4 j = i - g
5 while j >= 0 && A[j] > v
6 A[j+g] = A[j]
7 j = j - g
8 cnt++
9 A[j+g] = v
10
11 shellSort(A, n)
12 cnt = 0
13 m = ?
14 G[] = {?, ?,..., ?}
15 for i = 0 to m-1
16 insertionSort(A, n, G[i])
A function shellSort(A, n) performs a function insertionSort(A, n, g), which considers every g-th elements. Beginning with large values of g, it repeats the insertion sort with smaller g.
Your task is to complete the above program by filling ?. Write a program which reads an integer n and a sequence A, and prints m, Gi(i=0,1,...,m－1) in the pseudo code and the sequence A in ascending order. The output of your program must meet the following requirements:
1≤ m≤ 100
0≤ Gi≤ n
cnt does not exceed ⌈n^1.5⌉