insertion sort

Insertion Sort in Java and Complexity Analysis

Insertion sort consumes or marks one element in each iteration from the array of elements and grows the sorted output list.

At each iteration, insertion sort removes one element from the input array and insert that element in a location it belongs within the sorted list. And this is repeated until there are no elements remaining in the input array.

Insertion Sort Java Example

Output

At the end of each iteration, following the insertion of marked element in the sorted list, the elements with smaller indices are partially sorted.

It is twice as fast as bubble sort and somewhat faster than the selection sort in normal situations. It is often used with quicksort in final stages of more sophisticated sorts to achieve better performance.

Time Complexity

Let’s check how many number of comparisons and copies required by this algorithm.

In the first iteration, it compares maximum of one element in the array. In the second iteration, it compares maximum of two elements in the array, and so on, up to maximum of (n-1) comparisons.

If in each iteration an average of only half of the elements in the array are actually compared before finding the insertion point, then we can divide by 2 which gives

We can say approximately the number of copies is same as number of comparisons. Though, the copy operation here is not time consuming as compared to swap operation.

For some random data this algorithm runs twice as fast as bubble sort and faster than selection sort. So we can say insertion sort runs in O(n2) time for random data.

And for the input array which is already sorted or almost sorted it does much better, because the condition in the while loop will be never true, so it’s just a simple statement in the outer for loop which executes (n-1) times. So we can say the algorithms takes O(n) time to run in this case.

Space Complexity

Since you are sorting in place you don’t need any additional space for the data. Hence the space complexity of insertion sort is O(1).

Recommended Posts

References

  1. Different kinds of sorting
  2. Wikipedia sorting algorithm

Leave a Reply

avatar
  Subscribe  
Notify of