# Algorithm: Insertion Sort
###### tags: `Algorithm`

[TOC]

## What is Insertion Sort?

1. Save the element at position X.
**Note:** will start from position 1 or bigger.
2. Compare element X to the one on its left.
3. If element on left is bigger then swap.
4. Keep swapping until the element on left is smaller. (Step 2 & Step 3)
5. Input the saved element (Step 1)to the position in which the swapping stopped.

>**++Example:++**
>
[color=pink]

## How to implement Insertion Sort?

//Insertion Sort
public static void insertionSort(int array[]) { 
    int n = array.length;  
    for (int j = 1; j < n; j++) {  
        int key = array[j];  
        int i = j-1;  
        while ( (i > -1) && ( array [i] > key ) ) {  
            array [i+1] = array [i];  
            i--;  
        }  
        array[i+1] = key;  
    }  
}  

## Advantages & Disadvantages
>**Advantage:**
>Good for those small and almost sorted array [color=lightgreen]

>**Disadvantage:**
>Will increase time taken to sort when elements are a lot. [color=red]