Programming Tutorials and Interview Questions

- Implement Insertion Sort Algorithm in Java
- Java Program Code for Insertion Sort
- Pros and Cons of Insertion Sort
- Analysis of Insertion Sort
- References

*Insertion sort* executes in *O(N ^{2})* time, but in some situation it outperforms bubble and selection sort. It is about twice as fast as the bubble sort and somewhat faster than the selection sort while sorting a nearly sorted array.

Developing Java code for *insertion sort* is also not too complex, although *insertion sort* slightly more involved than the bubble and selection sorts. To sort a given array of items we pick an item, shift the remaining items, and then insert the picked item in the correct place. This process is repeated until all the items are in the correct sequence.
Following program develops a class `InsertionSort`

containing a `static`

generic method `insertionSort`

. Note that Java provides the `java.util.Comparable`

interface that contains a single method, `compareTo`

. Any class that correctly implements this interface guarantees a total ordering of its instances.

/* Java Program code for insertion sort */ class InsertionSort { public static <T extends Comparable<T>> void insertionSort (T[] list, int size) { int outCounter, inCounter; T temp; // Sort list[] into increasing order. for (outCounter = 1; outCounter < size; outCounter++) { temp = list[outCounter]; for (inCounter = outCounter; inCounter > 0 && list[inCounter - 1].compareTo(temp) > 0; inCounter--) { list[inCounter] = list[inCounter - 1]; } list[inCounter] = temp; } } } public class InsertionSortDemo { public static void main (String[] args) { Integer arr[] = {10, 9, 8, 7, 6, 6, 4, 3, 2, 1}; InsertionSort.insertionSort(arr, arr.length); System.out.println("Sorted Array: "); for(Integer i : arr) { System.out.println(i); } } } OUTPUT ====== Sorted Array: 1 2 3 4 6 6 7 8 9 10

In above implementation of `insertionSort`

, we do not exchange `list[inCounter]`

and ` list[inCounter - 1]`

in every iteration, rather we assign `list[outCounter]`

to `temp`

outside inner loop, and then use this `temp`

in comparison, and finally when control gets out of inner loop we assign `temp`

to `list[inCounter]`

. It saves number of assignments done in every iteration.

*Insertion sort* is a good choice when the array to be sorted is almost sorted. This is because there will be less number of swaps. On the contrary, insertion is slow because all the elements after an element that is not in order have to be moved up, therefore not good for big arrays that are not partially sorted.

In any case, the *insertion sort* runs in *O(N ^{2})* time for random data. For data that is already sorted or almost sorted, the

`for`

loop is never true, so it becomes a simple statement in the outer loop, which executes
However, for data arranged in inverse sorted order, every possible comparison and shift is carried out, so the *insertion sort* runs no faster than the bubble sort.

In this tutorial we discussed *insertion sort* and developed Java program code for *insertion sort*. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.