# Insertion Sort Algorithm

May 11, 2019

Its a kind of incremental insertion technique, where the algorithm build up sorting by first sorting n-1 items.

Or, we can say that we pick an element on n-1 items, and insert in a position where all items on the left side are less than or equal to this number.

## Insertion Sort Algorithm

The algorithm works in two loops, where outer most loop iterate over complete array. To be more precise, We iterate from index-1 to end of array. Leaving index-0 to be used by inner loop.

In inner loop, the loop variable takes the index from outer loop index variable. It takes a backup of the value present on that index, and go backward toward 0-index. It shift previous elements to next position unless they are greater than the value for which we have taken backup.

In short, inner loop tries to sort the n-1 part of array by shifting any bigger element to right. And, insert the element to the final position.

See the code here:

``````public void sort(int[] arr) {
int len = arr.length;
for (int i=1; i<len; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}

arr[j+1] = key;
}
}``````

## Key Points

• It does not use extra memory. And, is in-place algorithm.
• Its stable, as it does not change order of same value elements.
• It is more efficient in practice than Bubble Sort and Selection Sort
• It is well suited for small data sets.

## Runtime complexity

The algorithm runs on O(n^2) in worst case.

## Similar Posts

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

### Swap Nodes Pairs in Link List - Leet Code Solution

Problem Statement Given a linked list, swap every two adjacent nodes and return…

### What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

### Replace all spaces in a string with %20

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

### Reverse digits of a signed integer - Leet Code Solution

Problem Statement Given a signed integer, reverse digits of an integer. Return…

### Determine if a string has all unique characters

Problem Implement an algorithm to determine if a string has all the characters…

## Latest Posts

In this post, we will see some of the frequently used concepts/vocabulary in…

System design interview is pretty common these days, specially if you are having…

### Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

### Graph Topological Sorting - Build System Order Example

Graph Topological Sorting This is a well known problem in graph world…

### Binary Tree - Level Order Traversal

Problem Statement Given a Binary tree, print out nodes in level order traversal…

### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…