by BehindJava

# Data Structures - Insertion Sort Algorithm

Home » datastructures » Data Structures - Insertion Sort Algorithm

In this tutorial, we are going to learn about insertion sort in detail and its algorithmic implementation.

# Insertion Sort

• In-place algorithm.
• O(n^2) time complexity - Quadratic.
• It will take 100 steps to sort 10 items, 10000 steps to sort 100 items and 1000000 steps to sort 1000 items.
• Doesn’t require much swapping as bubble sort.
• Stable algorithm.

# Insertion Sort Algorithm

INSERTION_SORT (A, N)

1. Set A = -∞.
2. Repeat Step 3 to 5 for K = 2, 3, …, N:
3. Set TEMP = A[K] and PTR = K – 1.
4. Repeat while TEMP < A[PTR]:

1. Set A[PTR+1] = A[PTR]
2. Set PTR = PTR – 1. [End of Loop.]
5. Set A[PTR+1] = TEMP.
6. Return.

# Insertion Sort Programmatic Implementation in Java

``````public class InsertionSort {
public static void main(String[] args) {

int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
for (int firstUnsortedIndex = 1; firstUnsortedIndex < intArray.length; firstUnsortedIndex++) {
int newElement = intArray[firstUnsortedIndex];
int i;
for (i = firstUnsortedIndex; i > 0 && intArray[i - 1] > newElement; i--) {
intArray[i] = intArray[i - 1];
}
intArray[i] = newElement;
}
for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i]+ " ");
}
}}``````

Output:

``-22 -15 1 7 20 35 55 ``

# Insertion Sort Complexity

• This Sorting algorithm is frequently used when n is very small.
• Worst case occurs when array is in reverse order. The inner loop must use K – 1 comparisons.

• f(n) = 1 + 2 + 3 + ….+ (n – 1) = n(n – 1)/2= O(n^2)
• In average case, there will be approximately (K – 1)/2 comparisons in the inner loop.

• f(n) = 1 + 2 + 3 + ….+ (n – 1)/2 = n(n – 1)/4 = O(n^2)