---
title: "Explain shell sort"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:shell-sort-explain"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/shell-sort-explain
site: BCT Engineering
---

# Explain shell sort

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2075 Baisakh, 4 marks
- Video: [Sorts 5 Shell Sort](https://www.youtube.com/watch?v=ddeLSDsYVp8) — RobEdwards
- 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-explain
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Explain shell sort.

## Short answer

Shell sort improves insertion sort by first sorting elements far apart. It progressively reduces the gap (starting with n/2, then n/4, etc.), performing insertion sort on sub-lists formed by the gap. With gap 1, it becomes a final insertion sort on a nearly sorted list, giving O(n^2) worst-case time but faster in practice.

## Answer

**Shell sort** (Donald Shell, 1959) is an improvement of insertion sort. Insertion sort is slow because an element moves only one position at a time. Shell sort first compares and sorts elements that are far apart, then reduces the distance (gap) step by step, and ends with a gap of 1, which is an ordinary insertion sort on an almost-sorted list.

#### Steps
1. Choose a gap sequence, e.g. n/2, n/4, ..., 1 (Shell's original).
2. For each gap *g*: treat elements *g* positions apart as separate sub-lists and sort each sub-list with insertion sort.
3. Reduce the gap and repeat until the gap is 1 and the list is sorted.

```c
void shell_sort(int a[], int n) {
    int gap, i, j, t;
    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++) {
            t = a[i];
            for (j = i; j >= gap && a[j - gap] > t; j -= gap)
                a[j] = a[j - gap];          /* shift larger element */
            a[j] = t;
        }
}
```

#### Small example: 23 12 5 18, gap 2 then 1
- Gap 2: sub-lists (23, 5) and (12, 18) → 5 12 23 18.
- Gap 1: insertion sort → 5 12 18 23.

#### Properties
- In-place (O(1) extra space) and not stable.
- Time: worst O(n²) with Shell's gaps (better, e.g. O(n^1.5), with Knuth's gaps 1, 4, 13, 40, ...); best case near O(n log n).
- Good for medium-size lists because it is simple and fast in practice.

## Check yourself

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

1. How does shell sort improve on insertion sort?
   A. It sorts far-apart elements first with a gap, then reduces the gap down to 1
   B. It uses a heap
   C. It splits into halves and merges
   D. It uses buckets
   Answer: A. Elements move over large distances early, leaving an almost sorted list for the final gap-1 pass. (Key point: Idea)

2. What must the last gap be?
   A. n/2
   B. 2
   C. 0
   D. 1
   Answer: D. A gap of 1 is a plain insertion sort that guarantees a sorted list. (Key point: Final gap)

3. In a pass with gap g, what is sorted?
   A. Each block of g consecutive elements by selection sort
   B. Sub-lists of elements g positions apart, using insertion sort
   C. Only the first g elements
   D. The whole list by merging
   Answer: B. Elements g apart form sub-lists sorted by insertion sort. (Key point: Sub-lists)

4. Which is true of shell sort?
   A. Stable with O(n) extra space
   B. In-place and not stable
   C. Always O(n log n)
   D. Needs a sorted input
   Answer: B. Shell sort is in-place and unstable; worst case is O(n^2) with Shell's gaps. (Key point: Properties)

## Related in Data Structure and Algorithm

- [Shell sort on 92, 83, 22, 49, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ashell-sort-trace) — Data Structure and Algorithm, chapter 7