Insertion Sort Algorithm

Insertion sort algorithm is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

This works like the way we sort playing cards in our hands.

Insertion Sort
Insertion Sort Explanation
  • Worst-case performance :- О(n2) comparisons, swaps
  • Best-case performance :- O(n) comparisons, O(1) swaps
  • Average performance :- О(n2) comparisons, swaps
  • Worst-case space complexity :- О(n) total, O(1) auxiliary
Java Program of Insertion Sort Algorithm


Input Array before Insertion Sort. 80 15 60 30 20 90 Sorted Array after Insertion Sort. 15 20 30 60 80 90

Some theory part of this article uses material from the Wikipedia article “Insertion Sort”, which is released under the CC BY-SA 3.0.

Leave a Reply

Your email address will not be published. Required fields are marked *