Regarding shell sort algorithm

I am reading abook on algorithms. It is mentioned in shell sort as below

An important property of Shellsort (which we state without proof) is that an (h subscipt k) hk-sorted file that is then (h subsciprt (k-1)) hk-1-sorted remains hk-sorted. If this were not the case, the algorithm would likely be of little value, since work done by ea开发者_开发知识库rly phases would be undone by later phases.

My question is what does author mean by above statement?

Thanks!

Shell sort is a multi-pass sorting algorithm. It works by sorting a subset of the array at a particular integer "stride" value k, i.e. only accessing every kth element in the array.

Initially a large value for the stride is used, on subsequent passes this stride value is decreased until the final pass is run with a stride of 1 (which is typically just a standard insertion sort phase) and the array is fully sorted.

The statement you've asked about merely says that any sorting that was done on earlier passes (larger stride values) is preserved by later passes (smaller stride values). If this wasn't the case there would be no point in the multi-pass approach used by shell sort.

Hope this helps.