In this tutorial, we will learn how to implement Shell Sort in java. First, we will start by understanding the Shell Sort algorithm.

**Shell** **Sort Algorithm**

Shell sort is an **in-place** comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.

In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every **h**’th element are sorted.

## Time Complexity of Shell Sort:

**Best case:**`0(nlogn)`

**Average case:**`0(n(logn)^2)`

**Worst case:**`0(n(logn)^2)`

Before we begin, you need to have an idea of the following:

**Implementation of Shell sort in java**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | import java.util.Arrays; public class ShellSortJava { public static void main(String[] args) { int[] arr = { 23, 12, 89, 145, 10, 8, 333, 1, 70, 67 }; System.out.println("Array Before Sorting : "); System.out.println(Arrays.toString(arr)); System.out.println("Array After Shell Sorting : "); arr = shellsort(arr); System.out.println(Arrays.toString(arr)); } private static int[] shellsort(int[] array) { int h = 1; while (h <= array.length / 3) { h = 3 *h + 1; //h<=length/3 } while (h > 0) { // similar to insertion for (int i = 0; i < array.length; i++) { int temp = array[i]; int j; for (j = i; j > h - 1 && array[j - h] >= temp; j = j - h) { array[j] = array[j - h]; } array[j] = temp; } h = (h - 1) / 3; } return array; } } |

The **output **of shell Sort Algorithm in java: