Insertion sort is a sorting algorithm that sorts an array by splitting the array into an unsorted part and a sorted part. The values from the unsorted part will then be picked and moved into the correct position in the sorted part.
Best case: Ω(n) Average case: θ(n^2) Worst Case: O(n^2)