> For the complete documentation index, see [llms.txt](https://blog.sunilgudivada.dev/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/sorting/insertion-sort.md).

# Insertion Sort

## Java Implementation

```java
/*
==========================================================
Generic Implementation of Insertion sort
Input: Used Comparable interface as input

Input: [ 3, 0, 5, 2, 1, 0, 0, 0, 4 ]
Output: [ 0, 0, 0, 0, 1, 2, 3, 4, 5 ]

Input: [ "three", "0", "five", "2", "one", "seven", "4" ]
Output: [ "0", "2", "4", "five", "one", "seven", "three" ]

==========================================================
*/

public static class Insertion {
    public int partition(Comparable[] a, int low, int high) {
      int i = low, j = high + 1;
      while (true) {
        while (compare(a[++i], a[low])) if (i == high) break;
        while (compare(a[low], a[--j])) if (j == low) break;
        if (i >= j) break;
        swap(a, i, j);
      }
      swap(a, low, j);
      return j;
    }

    void sort(Comparable[] a, int low, int high) {
      if (low < high) {
        int pi = partition(a, low, high);
        sort(a, low, pi - 1);
        sort(a, pi + 1, high);
      }
    }

    private void swap(Comparable[] a, int i, int j) {
      Comparable swap = a[i];
      a[i] = a[j];
      a[j] = swap;
    }

    private boolean compare(Comparable comparable, Comparable comparable1) {
      return comparable.compareTo(comparable1) < 0;
    }
  }
```

{% hint style="success" %}

### Properties

* Stable
* $$O(1)$$ extra space
* $$O(n^{2})$$ comparisons and swaps
* **Adaptive**: $$O(n)$$ time when nearly sorted
* Very low overhead
  {% endhint %}