Insertion Sort Java Example

Insertion Sort is a simple and slow sorting algorithm that repeatedly takes the next element from the un-sorted section and inserts it into the sorted section at the correct position.

The idea of insertion sort comes from our daily life experiences. For example, when you play cards with your friends, you will insert the next card you pick into the sorted cards in your hand.

Insertion sort algorithm

The basic idea of insertion sort algorithm can be described as these steps:

1. Data elements are grouped into two sections: a sorted section and an un-sorted section.
2. Take an element from the un-sorted section.
3. Insert the element into the sorted section at the correct position based on the comparable property.
4. Repeat step 2 and 3 until no more elements left in the un-sorted section.

Insertion sort advantages

Though insertion sort is clearly slower than other sorting algorithms such as Merge Sort, but it has some good advantages in particular cases:

• Efficient for small data input sets
• It is adaptive i.e. efficient for data sets that are already substantially sorted
• It is stable; i.e. does not change the relative order of elements with equal keys
• It is online; i.e. can sort a list as it receives it

Insertion Sort Java Implementation

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		//This is unsorted array
		Integer[] array = new Integer[] {12,13,24,10,3,6,90,70};
		
		//Let's sort using insertion sort
		insertionSort(array, 0, array.length);
		
		//Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSort(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++) 
		{
			d = a[i];
			int j = i;
			while (j > fromIndex && ((Comparable) a[j - 1]).compareTo(d) > 0) 
			{
				a[j] = a[j - 1];
				j--;
			}
			a[j] = d;
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Insertion Sort Performance Improvement

If you look at previous implementation then you can easily identify that iterating over array to find correct spot inside already sorted array seems most time taking task and which can easily be improved using more fast search algorithm.

As we see that array is sorted already, so we can employ binary search algorithm which is more effective for already sorted arrays. So our improved insertion sort algorithm will become:

public class InsertionSortExample 
{
	public static void main(String[] args) 
	{
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

		// Let's sort using insertion sort
		insertionSortImproved(array, 0, array.length);

		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void insertionSortImproved(Object[] a, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = fromIndex + 1; i < toIndex; i++)
		{
			d = a[i];
			int jLeft = fromIndex;
			int jRight = i - 1;
			//Check if its current position is it's suitable position
			if (((Comparable) a[jRight]).compareTo(d) > 0) 
			{
				//Perform binary search
				while (jRight - jLeft >= 2) 
				{
					int jMiddle = (jRight - jLeft) / 2 + jLeft - 1;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				if (jRight - jLeft == 1) 
				{
					int jMiddle = jLeft;
					if (((Comparable) a[jMiddle]).compareTo(d) > 0) {
						jRight = jMiddle;
					} else {
						jLeft = jMiddle + 1;
					}
				}
				//Place the element
				int j = i;
				for (j = i; j > jLeft; j--) 
				{
					a[j] = a[j - 1];
				}
				a[j] = d;
			}
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Of course, it has more lines of code, but it will definitely improve performance of overall sorting time.

Happy Learning !!

Ref: https://en.wikipedia.org/wiki/Insertion_sort