Skip to main content

Shell sort on 92, 83, 22, 49, ...

Short answer

With gaps 5,2,1. Gap 5 sorts pairs at distance 5, producing 92 12 9 49 36 98 83 22 70 51. Gap 2 sorts even-indexed and odd-indexed sub-lists, giving 9 12 36 22 70 49 83 51 92 98. Gap 1 insertion sort completes sort: 9, 12, 22, 36, 49, 51, 70, 83, 92, 98.

Sort the numbers 92, 83, 22, 49, 36, 98, 12, 9, 70 and 51 using shell sort.

Use Shell's gap sequence n/2, n/4, ..., 1. With n = 10 the gaps are 5, 2, 1.

Original list: 92 83 22 49 36 98 12 9 70 51 (positions 0 to 9)

Pass 1: gap = 5 (compare a[i] and a[i+5])

Pair (positions)ValuesAction
0, 592, 98in order
1, 683, 12swap
2, 722, 9swap
3, 849, 70in order
4, 936, 51in order

Result: 92 12 9 49 36 98 83 22 70 51

Pass 2: gap = 2 (two sub-lists)

  • Even positions: 92, 9, 36, 83, 70 → sorted: 9, 36, 70, 83, 92
  • Odd positions: 12, 49, 98, 22, 51 → sorted: 12, 22, 49, 51, 98

Putting them back in position order: 9 12 36 22 70 49 83 51 92 98

Pass 3: gap = 1 (insertion sort)

InsertList after
129 12 36 22 70 49 83 51 92 98
369 12 36 22 70 49 83 51 92 98
229 12 22 36 70 49 83 51 92 98
709 12 22 36 70 49 83 51 92 98
499 12 22 36 49 70 83 51 92 98
839 12 22 36 49 70 83 51 92 98
519 12 22 36 49 51 70 83 92 98
929 12 22 36 49 51 70 83 92 98 (no change)
989 12 22 36 49 51 70 83 92 98 (no change)

Sorted list: 9, 12, 22, 36, 49, 51, 70, 83, 92, 98

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →