### How to Implement Shell Sort in C++ (With Code Example and Pseudocode)

**Shell Sort** is a fast, comparison-based sorting algorithm that improves upon **insertion sort** by allowing comparisons between elements that are far apart. This C++ implementation follows the same principles as Shell Sort in Python but leverages the speed and efficiency of C++. In this article, we’ll walk you through how Shell Sort works, provide pseudocode, show a C++ implementation, and include a detailed step-by-step walkthrough with a larger array example.

For comparisons with other sorting algorithms, pros and cons, and additional details, please refer to the **How to Do Shell Sort in Python** article.

## What is Shell Sort?

Shell Sort is an enhanced version of **insertion sort** that allows elements to move faster toward their correct positions by first comparing elements that are far apart (based on a gap). As the gap shrinks, the algorithm refines the sort until the gap is 1, at which point it performs a final insertion sort.

Shell Sort is efficient for medium-sized datasets and relies heavily on the choice of the gap sequence.

## How Shell Sort Works

**Initialize a gap**: The gap is usually set to half the size of the array.**Compare elements separated by the gap**: Perform an insertion sort on elements separated by the gap.**Reduce the gap**: After each pass, reduce the gap and repeat the process.**Perform final insertion sort**: Once the gap reaches 1, the algorithm finishes with a regular insertion sort.

## Shell Sort Pseudocode

Here’s the pseudocode for Shell Sort, adapted for C++:

ShellSort(array, n): gap = n // 2 # Initialize the gap while gap > 0: for i = gap to n - 1: temp = array[i] j = i # Perform insertion sort for the current gap while j >= gap and array[j - gap] > temp: array[j] = array[j - gap] # Shift larger elements to the right j = j - gap array[j] = temp # Insert temp in its correct location gap = gap // 2 # Reduce the gap

### Shell Sort in C++ (Code Example)

Here’s a C++ implementation of Shell Sort using the same logic as the pseudocode above:

#include <iostream> using namespace std; // Function to implement Shell Sort void shellSort(int arr[], int n) { // Start with a gap of n/2, then reduce the gap for (int gap = n / 2; gap > 0; gap /= 2) { // Perform insertion sort with the current gap for (int i = gap; i < n; i++) { int temp = arr[i]; int j; // Shift elements that are gap apart for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } // Place the temp element in its correct position arr[j] = temp; } } } // Utility function to print an array void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original array: "; printArray(arr, n); shellSort(arr, n); cout << "Sorted array: "; printArray(arr, n); return 0; }

**Output:**

Original array: 19 22 63 105 2 78 54 92 10 45 72 8 18 66 3 Sorted array: 2 3 8 10 18 19 22 45 54 63 66 72 78 92 105

### Step-by-Step Walkthrough of Shell Sort

Let’s walk through how Shell Sort works using the larger array `[19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3]`

.

**Step 1**: Initialize the Gap Sequence

- The initial gap is calculated as half of the array length (
`n // 2`

), which is`15 // 2 = 7`

.

**Initial gap**: 7

**Step 2**: Perform Insertion Sort for Elements with Gap 7

- We now compare and swap elements that are 7 positions apart.

**Array before sorting**:

[19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3]

- Compare
`arr[0] (19)`

and`arr[7] (92)`

: No swap. - Compare
`arr[1] (22)`

and`arr[8] (10)`

: Swap →`[19, 10, 63, 105, 2, 78, 54, 92, 22, 45, 72, 8, 18, 66, 3]`

. - Compare
`arr[2] (63)`

and`arr[9] (45)`

: Swap →`[19, 10, 45, 105, 2, 78, 54, 92, 22, 63, 72, 8, 18, 66, 3]`

. - Compare
`arr[3] (105)`

and`arr[10] (72)`

: Swap →`[19, 10, 45, 72, 2, 78, 54, 92, 22, 63, 105, 8, 18, 66, 3]`

. - Compare
`arr[4] (2)`

and`arr[11] (8)`

: No swap. - Compare
`arr[5] (78)`

and`arr[12] (18)`

: Swap →`[19, 10, 45, 72, 2, 18, 54, 92, 22, 63, 105, 8, 78, 66, 3]`

. - Compare
`arr[6] (54)`

and`arr[13] (66)`

: No swap. - Compare
`arr[7] (92)`

and`arr[14] (3)`

: Swap →`[19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92]`

.

**Array after first pass (gap 7)**:

[19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92]

**Step 3**: Reduce the Gap

- We reduce the gap by dividing it by 2:
`7 // 2 = 3`

.

**New gap**: 3

**Step 4**: Perform Insertion Sort with Gap 3

- Now we compare and swap elements that are 3 positions apart.
- Compare
`arr[0] (19)`

and`arr[3] (72)`

: No swap. - Compare
`arr[1] (10)`

and`arr[4] (2)`

: Swap →`[19, 2, 45, 72, 10, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92]`

. - Compare
`arr[2] (45)`

and`arr[5] (18)`

: Swap →`[19, 2, 18, 72, 10, 45, 54, 3, 22, 63, 105, 8, 78, 66, 92]`

. - Compare
`arr[3] (72)`

and`arr[6] (54)`

: Swap →`[19, 2, 18, 54, 10, 45, 72, 3, 22, 63, 105, 8, 78, 66, 92]`

. - Compare
`arr[4] (10)`

and`arr[7] (3)`

: Swap →`[19, 2, 18, 54, 3, 45, 72, 10, 22, 63, 105, 8, 78, 66, 92]`

. - Compare
`arr[5] (45)`

and`arr[8] (22)`

: Swap →`[19, 2, 18, 54, 3, 22, 72, 10, 45, 63, 105, 8, 78, 66, 92]`

. - Compare
`arr[6] (72)`

and`arr[9] (63)`

: Swap →`[19, 2, 18, 54, 3, 22, 63, 10, 45, 72, 105, 8, 78, 66, 92]`

. - Compare
`arr[7] (10)`

and`arr[10] (105)`

: No swap. - Compare
`arr[8] (45)`

and`arr[11] (8)`

: Swap →`[19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 105, 45, 78, 66, 92]`

. - Compare
`arr[9] (72)`

and`arr[12] (78)`

: No swap. - Compare
`arr[10] (105)`

and`arr[13] (66)`

: Swap →`[19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92]`

. - Compare
`arr[11] (45)`

and`arr[14] (92)`

: No swap.

**Array after second pass (gap 3)**:

[19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92]

**Step 5**: Reduce the Gap to 1 (Final Insertion Sort Pass)

- Now, reduce the gap to
`1`

(regular insertion sort).

**New gap**: 1

- Perform adjacent comparisons and swaps as necessary to complete the sorting.

**Array after final pass (gap 1)**:

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

#### Final Sorted Array:

After completing all gap reductions, the array is fully sorted:

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

**Advantages** **of Shell Sort**

**Improved performance**over basic sorting algorithms like insertion and bubble sort.**In-place sorting**with O(1) space complexity, making it memory-efficient.- Easy to implement and adapt to various gap sequences.

**Limitations** **of Shell Sort**

**Performance depends on the gap sequence**, and poor choices can lead to suboptimal performance.**Not stable**, meaning it may not preserve the relative order of equal elements.**Generally slower**than more advanced algorithms like quicksort and merge sort on large datasets.

For smaller and medium-sized datasets where memory usage is a concern, Shell Sort strikes a good balance between simplicity and efficiency.

### Conclusion

Shell Sort is a versatile and efficient sorting algorithm that builds on **insertion sort** by first sorting far apart elements, gradually reducing the gap until a final insertion sort is performed. It is particularly well-suited for **medium-sized datasets**, offering better performance than bubble or insertion sort, especially when the data is unsorted. Its simplicity and **in-place sorting** (O(1) space complexity) make it a good option when memory efficiency is critical.

Congratulations on reading to the end of this tutorial!

For more details on **Shell Sort’s comparison with other algorithms**, its **advantages and limitations**, and further explanations, please refer to the **How To Do Shell Sort in Python** article. This version covers Shell Sort in Python and compares it to algorithms like quick sort, merge sort, insertion sort, and more.

For further reading on sorting algorithms in C++, go to the articles:

- How To Do Heap Sort in C++
- How To Do Quick Sort in C++
- How To Do Selection Sort in C++
- How To Do Merge Sort in C++
- How To Do Comb Sort in C++
- How To Do Insertion Sort in C++
- How To Do Radix Sort in C++
- How To Do Bucket Sort in C++

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.