# 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.

- Divide the card into two section i.e, sorted and unsorted section by placing a marker after the first card.
- Repeat the 4 to 6 steps until unsorted section becomes empty.
- Select the first card from unsorted section.
- Swap the card to left until it arrives at the correct sorted position.
- 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

Now follow the above steps

**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 } }

# Advantages

- 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

**Download this sample code here**.

## Leave a Reply

Want to join the discussion?Feel free to contribute!