1.Begin
with a gap of g = Int(n/2)
2.Compare
items 1 and 1 + g, 2 and 2 + g, . . ., n
and n
- g. Swap any pairs that are out of order.
3.Repeat
Step 2 until no swaps are made for gap
g.
4.Halve
the value of g.
5.Repeat
Steps 2, 3, and 4 until the value of g is 0.