**Comb sort **is a **comparison based sorting** technique almost similar to Bubble Sort. We can say that comb sort is a **modified version of bubble sort**. In **bubble sort**, an adjacent pairs of elements are compared and swapped (if needed), unlike the bubble sort in comb sort the elements are compared with a particular gap.

The gap is decreased after each pass of sorting. **The decreasing factor is 1.3** i.e. after each pass the gap is **divided by 1.3** to get the new gap. It is an **in-place** sorting technique as it does not require any extra space to sort the data. The gapping of elements increases the efficiency of the sorting over bubble sort.

**PROCEDURE WITH EXAMPLE:**

Let take a **5 element** array as follows:

The array is to be sorted in **ascending order**. For the first time, the gap is **set to ****5** i.e. the number of elements of the array.

**Pass 1:**

**Before the first pass the array is:**

In the first pass, the gap will be **divided by 1.3**.

So, the gap = **5/1.3 = ****3**. The elements at **gap 3 will be compared** with each other and will be swapped (if necessary).

Firstly, the starting **index is 0** and it will be **compared with the index (0 + 3) = ****3.**

So, here, **89 ****will be compared with ****9**, as **9**** is ****lesser**** than ****89 **they will be **swapped** and we will get the array as:

After this, the element of **index 1 ****will be compared with index (1 + 3) = ****4**, as **-12 ****and ****21**** will be compared** again but as **-12 is already lesser than 21** then there will be **no swap** and the array will remain unchanged.

Next, **index 2** should be compared with **index (2 + 3) = ****5** but as **index 5 does not exist** so the iteration will be ended and it will go for the **next iteration**.

**Pass 2:**

In the **2nd pass**, the **gap will be again divided by ****1.3**.

So, in this pass the **gap = 3/1.3 = ****2**, so in a similar way, the elements at gap 2 will be compared with each other and will be swapped (if necessary).

**At first**, the element of starting **index 0**** will be compared** with the element of the **index (0 + 2) = ****2. **Here **9**** is ****lesser**** than ****17** so there will be **no change**.

After this the elements of **index 1**** and index (1 + 2) = ****3**** will be compared**. In that case, **-12** is already **lesser** than **89**, so there will be **no swapping**.

Next **index 2 ****will be compared** with **index**** (2 + 2) = ****4. **Here now, **17**** will be compared with ****21**, as **17 **is **lesser** than **21** so there will be **no swapping.**

Next, **index 3**** should be compared with index (3 + 2) = ****5** but as **index 5 does not exist** so the iteration will be ended and it will go for the next iteration.

**Pass 3:**

In the **3rd pass**,** ****the gap** will be again **divided by 1.3**.

So, in this pass the **gap = 2/1.3 = ****1**, so in a similar way, the elements at gap 1 will be compared with each other and will be swapped (if necessary).

For the first time **index 0 ****will be compared with index (0 + 1) = ****1**. For this iteration, each pair of adjacent elements **will be compared**. Here **9 ****is compared with ****-12**, as **-12** is **lesser** than **9**, so it will be **swapped**.

**Here**, the **next **two adjacent elements **9 **and **17** will be **compared** and will **not be swapped** as they are already in **sorted order**.

**The next**** two adjacent** elements are **17 ****and ****89**, they will be **compared **with each other but there will be **no swapping**.

The last adjacent pair is **89**** and ****21**, they will be **compared** with each other but as **89**** is greater than ****21 **then there will be **swapping** and the array will be:

**The array is already sorted** after this pass.

For **implementing the comb sort ****one flag** is used in the loop to check whether any **swapping has done or not**. If there is any swapping then only the loop will go for the next pass.

Hence, **though the array is sorted** we have to go for the **next pass**.

**Pass 4:**

Here the gap is **1/1.3 = ****0.**

That means each element of the array will be compared to itself only. There will be **no swapping**. So, the **loop will ****stop executing**. So, the final sorted array is:

```
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 comb sort]
Set g<-n
Set f<-1
While g≠1 or f=1 repeat
Set g<-(g*10)/13
If g<1 then
Set g <- 1
[End of ‘If’]
Set f<-0
For i = 0 to n-g repeat
If arr[i] > arr[i+g] then
Set t<-arr[i]
Set arr[i]<-arr[i+g]
Set arr[i+g]<-t
Set f <- 1
[End of If]
[End of for loop]
[End of while loop]
Step 3: [Displaying the array elements]
For i=0 to n repeat
Print arr[i]
Step 4: Stop.
```

__CHARACTERISTICS:__

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

**2.** It is an in-place sorting algorithm as it does not require any extra storage space for sorting.

**3.** It is similar to bubble sort but efficiency is better than bubble sort.

**4.** The sorting is done by swapping the elements at a particular gap if they are not incorrect order. After each pass, the gap is reduced.

__TIME COMPLEXITY:__

The best case will occur if the array is already sorted, then at the first pass, there will be no swapping. The loop is written such that if there is no swapping the loop will be ended and will not be executed from the next iteration.

The **worst-case** will occur if the array is in descending order.

__SPACE COMPLEXITY:__

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

__ADVANTAGES:__

**1.** It does not require extra spaces to sort the elements.

**2.** It works better than bubble sort though both are similar.

**3.** The logic is simple and it is reliable.

__DISADVANTAGES:__

**1.** Worst-case complexity is the same as the complexity of bubble sort.

**2.** Does not work well for a large number of data.

**3.** It is not a stable sort.

__APPLICATION:__

It is an improved version of bubble sort so it is applied in some applications for sorting instead of **bubble sort**.

Related

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

Contributed by