# Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. We use this algorithm while we play any games of cards. So to remember insertion sort always remember sorting deck of cards.

# Steps that we use to sort decks of cards.

1. Divide the card into two section i.e, sorted and unsorted section by placing a marker after the first card.
2. Repeat the 4 to 6 steps until unsorted section becomes empty.
3. Select the first card from unsorted section.
4. Swap the card to left until it arrives at the correct sorted position.
5. Move the marker to the right.

Let’s understand the above steps with a simple exaplanation of cards. Assume we have a deck of 5 cards.
Cards : 6 7 3 2 5

6 | 7 3 2 5
Compare 7 to its left cards until it arrives at the correct position. Here it is already at correct position, so no movement
Move the marker.

6 7 | 3 2 5
Compare 3 to its left cards until it arrives at the correct position.
3 6 | 7 2 5
Move the marker.

3 6 7 | 2 5
Compare 2 to its left cards until it arrives at the correct position.
2 3 6 | 7 5
Move the marker.

2 3 6 7 | 5
Compare 5 to its left cards until it arrives at the correct position.
2 3 5 6 | 7
Move the marker

2 3 5 6 7 |
We got the sorted cards.

Let’s have a code to implement the above logic. As we set the marker at first position, so out first loop start from 1 and second loop runs from 1 to the number of cards left to marker.
InsertionSort.java

```package com.javalatte.itcuties.insertionsort;

public class InsertionSort {

public static void main(String[] JavaLatte) {
int cards[] = {6, 7, 3, 2, 5};
int noOfCard = cards.length;
//we place marker from 6, so first loop start at index 1
for (int marker = 1; marker < noOfCard; marker++) {
//j runs from 0 to no of element left to marker
for (int j = 0; j < marker; j++) {
if (cards[marker] < cards[j]) {
//swap elements
int tmp = cards[marker];
cards[marker] = cards[j];
cards[j] = tmp;
}
}
}
//sorted output
for (int i = 0; i < noOfCard; i++) {
System.out.print(cards[i] + " ");
}
System.out.println();//new line
}
}
```

InsertionSortWhileLoop.java

```package com.javalatte.itcuties.insertionsort;

public class InsertionSortWhileLoop {

public static void main(String[] JavaLatte) {
int cards[] = {6, 7, 3, 2, 5};
int noOfCard = cards.length;
//we place marker from 6, so first loop start at index 1
int marker = 1;
while (marker < noOfCard) {
//j runs from 0 to no of element left to marker
int j = 0;
while (j < marker) {
if (cards[marker] < cards[j]) {
//swap elements
int tmp = cards[marker];
cards[marker] = cards[j];
cards[j] = tmp;
}
j++;
}
marker++;
}
//sorted output
for (int i = 0; i < noOfCard; i++) {
System.out.print(cards[i] + " ");
}
System.out.println();//new line
}
}
```

• Simple implementation
• Efficient for (quite) small data sets
• Only requires a constant amount O(1) of additional memory space.
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n).

# Performance

• Worst Case Complexity: O(n^2) When array sorted in reverse order.
• Average Case Complexity: O(n^2)
• Best Case Complexity: O(n) When is array is already sorted
• 