Insertionsort
Insertion sort 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. However, insertion sort provides several advantages
Time Complexity:
Best Case: O(n)Average: O(n2)
Worst Case: O(n2)
Insertion sort iterates, consuming one input element each repetition,
and grows a sorted output list. At each iteration, insertion sort removes
one element from the input data, finds the location it belongs within the
sorted list, and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted
list behind it. At each array-position, it checks the value there against the largest
value in the sorted list (which happens to be next to it, in the previous array-position
checked). If larger, it leaves the element in place and moves to the next. If smaller, it
finds the correct position within the sorted list, shifts all the larger values up to make a
space, and inserts into that correct position.