Insertion Sort

Simplest and non efficient.

This is the algorithm used when sorting manually the playing cards. Take one care. Take second case and insert into the sorted position. Cards in hand will always be sorted. Take third case and insert it into the 'right' sorted position, and so on.

Complexity: O(n²)

Improvement: Searching before inserting can be reduce to log(n) by binary search. Thus the no of comparisons are nlongn. But after comparion, the movement might be n. So because of this movement in array, the complexity remains O(n²)

Benefits:

1. In Place. Required O(1) memory.

2. Online. Can be done as soon as elements are received.

Notes:

1. Would not use it. Use ?? instead.