---
title: "Shell sort on 92, 83, 22, 49, ..."
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:shell-sort-trace"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/shell-sort-trace
site: BCT Engineering
---

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

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2075 Baisakh, 4 marks
- Video: [shell sort example step by step|shell sort example in data structure](https://www.youtube.com/watch?v=BJh7uWDJsyU) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/shell-sort-trace
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

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

## 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.

## Answer

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) | Values | Action |
|---|---|---|
| 0, 5 | 92, 98 | in order |
| 1, 6 | 83, 12 | swap |
| 2, 7 | 22, 9 | swap |
| 3, 8 | 49, 70 | in order |
| 4, 9 | 36, 51 | in 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)
| Insert | List after |
|---|---|
| 12 | 9 12 36 22 70 49 83 51 92 98 |
| 36 | 9 12 36 22 70 49 83 51 92 98 |
| 22 | 9 12 22 36 70 49 83 51 92 98 |
| 70 | 9 12 22 36 70 49 83 51 92 98 |
| 49 | 9 12 22 36 49 70 83 51 92 98 |
| 83 | 9 12 22 36 49 70 83 51 92 98 |
| 51 | 9 12 22 36 49 51 70 83 92 98 |
| 92 | 9 12 22 36 49 51 70 83 92 98 (no change) |
| 98 | 9 12 22 36 49 51 70 83 92 98 (no change) |

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

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. For n = 10, which gaps does Shell's sequence n/2, n/4, ..., 1 give?
   A. 10, 5, 1
   B. 5, 2, 1
   C. 5, 3, 1
   D. 2, 1
   Answer: B. 10/2 = 5, 5/2 = 2, 2/2 = 1. (Key point: Gap sequence)

2. After gap 5 on 92 83 22 49 36 98 12 9 70 51, which pairs swap?
   A. Positions (1,6) and (2,7)
   B. Positions (0,5) and (3,8)
   C. Positions (4,9) only
   D. No pairs
   Answer: A. 83>12 and 22>9 swap; the others are already in order. (Key point: Pass 1)

3. What is the gap-1 pass?
   A. A merge
   B. An ordinary insertion sort on an almost-sorted list
   C. A selection sort
   D. A bucket distribution
   Answer: B. The final pass is insertion sort. (Key point: Gap 1)

4. What is the final sorted list?
   A. 9, 12, 22, 36, 49, 51, 70, 83, 92, 98
   B. 9, 12, 22, 36, 49, 70, 51, 83, 92, 98
   C. 98, 92, 83, 70, 51, 49, 36, 22, 12, 9
   D. 12, 9, 22, 36, 49, 51, 70, 83, 92, 98
   Answer: A. All ten numbers in ascending order. (Key point: Result)

## Related in Data Structure and Algorithm

- [Heap sort on 37, 33, 26, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-construct-12-element) — Data Structure and Algorithm, chapter 7
- [Radix sort on 32, 45, 60, 83, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-32-45-60) — Data Structure and Algorithm, chapter 7
- [Merge sort on 85, 76, 46, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-85-76) — Data Structure and Algorithm, chapter 7
- [Explain shell sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ashell-sort-explain) — Data Structure and Algorithm, chapter 7
- [B-tree of order 5 for 82, 12, 22, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-order5-82-12-22) — Data Structure and Algorithm, chapter 6, asked 2×
- [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Conductor selection, 100 MW 70 km 132 kV](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aconductor-selection-100mw-70km-132kv) — Transmission and Distribution System Design, chapter 4
- [Chi-square test on 100 random numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Achi-square-uniformity-100-numbers) — Simulation and Modeling, chapter 6
- [Chi-square uniformity test, 40 numbers](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Achi-square-uniformity-table-2074) — Simulation and Modeling, chapter 6
- [Line spectra of 12 + 6sin(140πt+30°) - 9cos(80πt-70°)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-spectrum-12-6sin) — Data Communication, chapter 3