**Shell sort **is a comparison-based sorting technique in which the **elements of a ****particular distance ****(or gap) are compared with each other and according to the order of sorting their values are swapped**.

It is **different from **a **bubble or selection sort**. It is an **in-place** sorting algorithm where no extra memory space is required to sort the data. After **each pass of sorting the gap is reduced** and the sorting continues till the **gap between the two elements reaches ****0**.

The **gap between ****two elements** decreased depending on the sequence used to sort. The original sequence of gapping is n/2, n/4, n/8, ….., 1 where n is the number of elements of the array. There are some other sequences also which can be used to sort the elements. They are:

**1. Knuth’s increments****:** 1, 4, 13, …, (3k – 1) / 2

**2. Pratt****: **1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

**3. Sedgewick’s increments****:** 1, 8, 23, 77, 281, 1073, 4193, 16577...4j + 1+ 3·2j + 1.

**4. Papernov & Stasevich increment****:** 1, 3, 5, 9, 17, 33, 65,...

**5. Hibbard’s increments****: **1, 3, 7, 15, 31, 63, 127, 255, 511…

__PROCEDURE WITH EXAMPLE:__

Suppose there is an array that has **8 elements** as follows:

The array should be sorted in **ascending order**. In this sorting, the original **sequence of gapping ****is used** i.e. **n/2 , n/4, n/8, … , 1**

So here **n=8** (**total number of elements**)

For the **first pass** the **gap**= **n/2 = 8/2** = **4**

So, first the **first element** of the array i.e. **56**** is compared** with the element at **index 4**, here the **element is 43**. As **43**** is lesser than ****56** so, **swapping required** and **56 will be stored at**** index 4** of the array. And as the interval is 4 so no other element is there to compare so **43 will be stored at 0th** position and the array will be:

Now, the **second gap** is n/4 = 8/4 =2 similarly **78**** will be compared with ****12** and as **12 is lesser than 78** they will also **be swapped** and the array will be:

Here, **between ****34**** and ****69**, **34 ****is already**** lesser than 69** so there will be **no swapping**. So the array will remain **unchanged**.

Now, the last pair i.e. **67**** and ****54 ****will be compared** and will **be swapped** and after 1st pass we will get the array:

In the second pass, the gapping is **n/4 = 8/4 = ****2**

Before the **2nd pass** the array is:

First, **43**** is compared to ****34**. As **34**** is ****l****esser than ****43** so it will be **swapped.** And the array will be:

**12**** and ****54**** will be compared** next but as there is **no swapping** the array will remain same.

This step will be a **little different** from the previous steps. In this step **56**** and ****43**** will be compared first** (i.e. **index 4** and **index 2**) here **no change** will be performed but **again ****43**** will be compared with ****34** (i.e. **index 2** with **index 0**), as **34**** is also lesser than ****43** so there will be **no change**. That means all the elements of the array of the same interval from right to left will be compared in a similar way so the array will remain the same.

Here also **78**** will be compared to ****54** and again **54 **will be **compared** to **12**. But as they are **incorrect order** so there will be **no change**.

In this step **69**** will be compared with ****56**, **56**** will be compared with ****43**,** **and **43 ****will again be compared with ****34**, all these elements are in the correct order so there will be **no change**.

**Firstly ****67**** is compared with ****78**, as **67**** is lesser than ****78** so it will be **swapped**. Now **67**** will be compared to ****54** but as **67**** is greater than ****54** so **there will be ****no swapping**. The **67**** will be placed at the position of ****78**** **and the array will be:

Here the gap is: **n/8= 8/8 = ****1**. So here the adjacent elements will be compared.

Before starting the sorting the array is:

Here, **34**** will be compared to ****12**. As **12**** is lesser than ****34**, it will be **swapped**. After swapping the array will be:

Here, **43**** will be compared to ****34**,** **and **34**** will be compared to ****12**. As they are in the correct order so there will be **no change**.

Here also the array is already in sorted order. **Similarly in the next steps**,** the array elements** will be compared by the following steps:

```
INPUT: An unsorted array a[6,2,4,1,…………….,n]
OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the inputs from the user]
Read n
for i=0 to n repeat
read arr[i]
Step 2: [Sorting the elements using shell sort]
Set step<-n/2
While step>0 repeat
For i=step to n repeat
Set tmp<-arr[i]
For j=i to j>=step and arr[j-step]>tmp repeat
Set arr[j]<-arr[j-step]
Set j<-(j-step)
Set arr[j]<-tmp
Set step<-step/2
Step 3: [Displaying the array elements]
For i=0 to n repeat
Print arr[i]
Step 4: Stop.
```

__CHARACTERISTICS:__

**1.** This is a comparison based sorting technique.

**2.** This sorting is done by comparing the elements at a particular interval.

**3.** This is an in-place sorting algorithm, no extra space is needed to sort the data.

**4.** It is a highly efficient sorting algorithm.

**5.** Shell sort is not a stable sort.

__TIME COMPLEXITY:__

The time complexity of the **shell sort** **depends on the ****sequence of gapping used ****in the sorting technique**.

Here, the original **sequence of shell sort i.e. ****n/2, n/4, n/8, ….. , 1** is used as a gapping sequence to sort the elements of the array. Hence in the best case the number of comparisons in each interval will be:

The **average case complexity** is also **O(n*logn)** in a similar way as the best case.

The **worst case** of shell sort occurs when the elements are totally in the opposite order. So for n number of elements, the last pass will be working as the bubble sort.

But this complexity depends on the sequence used to sort the data.

__SPACE COMPLEXITY:__

**Space complexity **of shell sort is **O(1)** as it does not require any extra space to sort the data.

__APPLICATION:__

**1.** A shell sort can be implemented using a small code, it is used in some applications to sort data instead of using the quick sort.

**2.** It can also be used to sort a subarray in some other sorting techniques to reduce the time and make the sorting faster.

__ADVANTAGES:__

**1.** The code is smaller than quick sort, merge sort, or heap sort.

**2.** It does not use any additional memory space.

**3.** The performance of shell sort is decent in worst case also.

**4.** It is faster than bubble sort and insertion sort.

__DISADVANTAGES:__

**1.** Though the code is simpler it is not efficient as the merge sort or quicksort.

**2.** It is slower than the sorting algorithms of similar complexity.

**3.** It is not a stable sorting algorithm.

Related

- Cocktail Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Quick Sort using recursion
- Quicksort Iterative
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Insertion Sort
- Selection Sort
- Bubble Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort

Contributed by