Insertion sort is another simple sorting algorithm, which can be used to sort any linear data structure like array and linked list. On simplicity this is next to bubble sort, and it’s also pretty close to how humans manually sort something (for example, a hand of playing cards). As name suggest, Insertion sort is based upon

*insertion of element in a sorted list*. To start, we assume that first element is already sorted. Then we pick next element and put it on second place, we compare this number with first element and if they are not in sorted order, we swap them. This gives a new sorted list of 2 elements. Now we pick third element and put it on 3rd place and compare it with 2nd placed number, if they are not in sorted order, we swap them, if all three elements are still not in sorted order then we again swap 1st and 2nd element, now we have a sorted list of three numbers. So in best case, we just need one comparison and no swapping, while In worst case we need to compare new number with each number in the sorted list i.e. k comparison, and k -1 swapping, where k is the length of sorted list. I think Insertion sort is pretty easy to understand, isn't it; if you still don't get remember how you arrange your hand of cards, first you pick one card, then pick next card and put it after first card if it is bigger or before first card if it is smaller; then you pick another card and insert it to its proper position. One more real world example of insertion sort is how tailors arrange shirts in cupboard, they always keep sort in sorted order of size and insert new shirt at right position. By the way if you notice trend then you can see that as length of our sorted list increased, so as number of comparison and swapping, which means this this sorting algorithm is*not suitable for large data set*. Indeed, it’s not as good as quicksort, heap sort or merge sort for sorting large arrays, but it’s good enough to sort small integer arrays where cost of comparison is small. By the way this algorithm is not just bound to numbers or integers, you can also sort String array with insertion sort or any list of Employee, depending they implement Comparator or Comparable to provide comparison logic. Insertion sort can also be used to sort any List of elements in Java. We will see more advantages and disadvantage of insertion sort in last section for now let's see pseudo code for insertion sort.