# Shell sort

## 1.Shell sort

* 是insertion sort的改良, 又稱為增量遞減排序排序法 (diminishing increment sort), 謝耳排序法
* 將原本的list藉由"increment"來切成sub-list
  * 每個sub-list皆用insertion sort來排序
  * 逐漸降低Increment直到等於1
  * 利用前一次排序的成果來加快排序
* The cool thing is that since that since the list was almost sorted it's far easier to get to a fully sorted state with increment set to 1.
  * Shell sort的表現比Insertion sort好

## 2.**Procedures**

## 3.Example code (Java)

* Modified insertion sort
  * Insertion sort takes in a start index and an increment
  * All iterations through the list are based on the increment
  * Adjacent elements separated by an increment are compared
  * Break out of the inner loop if no element is swapped

```
public static void insertionSort(int[] listToSort, int startIndex, int increment) {
    for (int i = 0; i < listToSort.length; i = i + increment) {
        for (int j = Math.min(i + increment, listToSort.length - 1)
             j - increment >= 0;
             j = j - increment) {
            if (listToSort[j] < listToSort[j - increment]) {
                swap(listToSort, j, j - increment);
            } else {
                break;
            }
        }
        print(listToSort);
    }
}
```

* Shell sort&#x20;
  * Picked an increment at random
  * Slowly reduce the increment

```
public static void shellSort(int[] listToSort){
    int increment = listToSort.length / 2;
    while (increment >= 1) {
        for (int startIndex = 0; startIndex < increment; startIndex++) {
            insertionSort(listToSort, startIndex, increment);
        }
        increment = increment / 2;
    }
}
```

## **4.Complexity**

* **Getting the exact complexity of Shell sort is hard** because it depends on the increment values chosen
* It's also not clear what the best increment value is.
* The complexity of Shell sort is better than insertion sort as the final iteration sort with increment = 1 has to work with a nearly sorted list.
  * The complexity of Shell sort is somewhere between O(N) and O(N^2)
  * Different value of increments produce different complexities&#x20;
* The algorithm is adaptive since it's based on insertion sort which is adaptive.
* It takes O(1) extra space, it sorts in space (No extra space)
  * 因為用原本的list儲存 (in-place 演算法)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/shell-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.