0

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 early phases would be undone by later phases.

My question is what does author mean by above statement?

Thanks!

4
  • 3
    Having a look at your previous questions makes me think... You seem to be asking us about a lot of stuff from this "book". Perhaps you should get a different one which you understand better?
    – flight
    Commented Sep 9, 2011 at 13:07
  • Which parts of the above statement do you understand? For example do you need someone to tell you what h<sub>k</sub>-sorted means, or not? Commented Sep 9, 2011 at 13:10
  • It sounds like a complicated way of saying that the intermediate steps of shell sort is a stable sort. I'm not confident enough about this to post as an answer though. I agree with quasiverse, get a better book that explains things in english rather than academic jargon.
    – Charles Ma
    Commented Sep 9, 2011 at 13:11
  • This is actually a good question. It's difficult to find an online proof of the assertion, and it's not obvious. Here is some proof, but for the key idea it refers only to Knuth, vol. 3. "Proposition: Let g, h be natural numbers. A g-sorted sequence remains g-sorted after h-sorting it."
    – cdunn2001
    Commented Sep 10, 2022 at 16:47

1 Answer 1

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.