> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/shell-sort.md).

# 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 演算法)