Shell Sort problem

Question

Show the result of running Shell Sort on the input 9,8,7,6,5,4,3,2,1 using increments { 1,3,7 }.

I have done this part. the result is:

9 8 7 6 5 4 3 2 1 (original)
2 1 7 6 5 4 3 9 8 ( 7-sort )
2 1 4 3 5 7 6 9 8 ( 3-sort )
1 2 3 4 5 6 7 8 9 ( 1-sort )

Then the question requires me to determine the running time of Shell Sort using Shell's increments of N/2, N/4, ..., 1 for sorted input.

I am not quite sure how to answer the second question as I don't understand the requirement of this question. So, would anyone give some hints to let me finish this question? Thank you for your help first!

Answer 1

Since N = 9, you need to show the result of a 4-sort, a 2-sort and a 1-sort.