- Partition the array into two subarrays - the first value will be the "sorted" array, and the others will be in an "unsorted" array.
- Take the first value
`x`in the unsorted array and store into a`temp`

. - Moving down the list in the sorted array, shift over every element greater than
`x`. - Insert
`x`and repeat.

Here's a nifty animation for your better learning.

Insertion sort is the best choice when data is nearly sorted or the problem size is small. Thus, it's a good choice for higher divide-and-conquer sorting algorithms such as merge sort and quick sort.

Furthermore, it is considered to have low overhead since it avoids executing unneccesary lines of code.

Insert sort is stable sorting algorithm.

If our array is already sorted, only `n-1` comparisons are used. In the worst case, `n(n-1)/2` comparisons are used. Time: `O(n ^{2})` Space:

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

```
import java.util.Arrays;
public class InsertionSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
insertionSort(testInt);
System.out.println(Arrays.toString(testInt));
}
public static void insertionSort(int[] test) {
/**
* The array will be partitioned to two subarrays - the sorted
* and unsorted. The first element will be in our sorted subarray.
*/
for (int i = 1; i < test.length; i++) {
// Store the element to insert
int temp = test[i];
/**
* For every element in our sorted subarray that is greater
* than the temp, shift elements over one.
*/
for (int j = i-1; j >= 0; j--) {
if (temp < test[j]) {
test[j+1] = test[j];
} else {
test[j+1] = temp;
break;
}
}
}
}
}
```

A handy guide of sorts for any computer science professional, Data Structures And Algorithms Made Easy in Java: Data Structure And Algorithmic Puzzles is a solution bank for various complex problems related to data structures and algorithms. It can be used as a reference manual by those readers in the computer science industry.

$ Check price(339+ reviews)

Cracking the Coding Interview will tell you exactly what you need to know to land your dream job at Google, Amazon, Microsoft or any other big tech companies. Packed with over 189 interview questions and detailed solutions, this book will help you train for the classic white-board technical interview. A must have for any CS major.

$ Check price(266+ reviews)

Ad