> 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/insertion-sort.md).

# Insertion sort

## 1.Insertion sort

* Start with a sorted sub-list of size 1
* Insert the next element into the sorted sub-list at the time right position. Now the sorted sub-list has 2 elements.
* By inserting into a sorted sub-list at every step the sub-list soon grows to be the entire list
* 將每一個元素與右邊的元素比較, 一旦右邊的比較小, 則開始swap (跟bubble sort很像)

## **2.Procedures**

* Insertion sort first assumes a sorted list of size 1 and inserts additional elements in the right position

## **3.Example code (Java)**

* Insertion method

```
public static void insertionSort(int[] listToSort) {
    //Go up to the second to last element
    for (int i = 0; i < listToSort.length - 1; i++) {
        //Consider everything uptil the ith element sorted
        //Bubble the element element outside the sorted sub-list to the right position
        for (int j = i + 1; j > 0; j--) {
            if (listToSort[j] < listToSort[j - 1]) {
                swap(listToSort, j, j - 1);
            } else {
                //If no swap was performed the element has been moved to the right position so break out the loop
                break;
            }
        }
        print(listToSort);
    }
}
```

* Swap

  ```
  public static void swap(int[] listToSort, int iIndex, int jIndex) {
      int temp = listToSort[iIndex];
      listToSort[iIndex] = listToSort[jIndex];
      listToSort[jIndex] = temp;
  }
  ```

## **4.Complexity**

* Complexity of Bubble sort is O(N^2)
* Checking "N" elements for each of "N" selected elements
* It's adaptive sort
* It takes O(1) extra space, it sorts in space (No extra space)
  * 因為用原本的list儲存 (in-place 演算法)
* It is a stable sort:
  * As entities bubble to the correct position in the sub-list that is sorted. The list the original order of entities are maintained for equal elements.
* It makes O(N^2) comparisons and O(N^2) swaps (與Bubble sort相同)
  * 比較複雜度是O(N^2)
  * 交換次數是O(N^2)

## **5.Insertion sort v.s bubble sort**

1. Bubble sort requires an additional pass over all elements to ensure that the list is fully sorted.
2. **Bubble sort has to do "N" comparisons at every step**. Insertion sort can stop comparison elements when the right position in the sorted list is found.
3. Bubble sort performs poorly with modern hardware because of the number of writes and swaps that it performs. Results in cache misses so has greater overhead than insertion sort.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.