Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted"
the claim follows easily from a careful definition of "k-sorted". define k-sorted as "for all i there does not exist a j > k such that for two elements in the list a[i+j] &lt; a[i]." then if a list is k-sorted, it is h-sorted for h > k.  

to look into deeper/ more general theory realize that k-sorted is a "measure of disorder" eg as in question how to measure sortedness. see this paper a survey of adaptive sorting algorithms, / Castro, Wood, measures of disorder, sec 1.2. h-sorted appears to be equivalent to measure #1, Dis, "largest distance determined by an inversion".