# 1. Introduction

*Shell Sort* is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.

# 2. Program Steps

1. Choose a gap sequence. A common choice is *n/2* for the initial gap, where *n* is the length of the array, then keep halving the gap until it becomes 1.

2. Compare elements separated by the gap distance and swap them if they are in the wrong order.

3. Repeat the process for each gap value until the smallest gap (usually 1) is used, which finalizes the sort.

# 3. Code Program

```
public class ShellSort {
// Function to sort array using shell sort
public static void shellSort(int arr[]) {
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
for (int i = gap; i < n; i++) {
int temp = arr[i];
// Shift earlier gap-sorted elements up until the correct location for arr[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// Place temp (the original arr[i]) in its correct location
arr[j] = temp;
}
}
}
// Driver method
public static void main(String args[]) {
int arr[] = {12, 34, 54, 2, 3};
System.out.println("Array before sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
shellSort(arr);
System.out.println("Array after sorting:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

### Output:

Array before sorting: 12 34 54 2 3 Array after sorting: 2 3 12 34 54

# 4. Step By Step Explanation

1. *shellSort* function: This function sorts the given array using the Shell Sort algorithm. It starts with a large gap (initialized as half the array length) and keeps reducing it until the gap becomes 1.

2. Inside the main loop, for each *gap* value, we perform a modified insertion sort. The element at the current position is stored in *temp*, and then by comparing elements that are *gap* distance apart, we shift elements to their correct positions.

3. The inner loop keeps comparing and shifting elements until the correct position for the current element (held in *temp*) is found, upon which it's placed in the correct position.

4. The process is repeated for all gaps until the smallest gap (1) is used, ensuring the entire array is sorted.

This method provides a balance between the slow insertion sort and a faster sorting method, taking advantage of a gapped approach to sort elements in fewer iterations.