Insertion sort can be improved.
By taking the difference between: the largest element - the next un-sorted element,
then compare if that difference to the largest sorted element,
if that difference is large, then start from the short end as usual,
BUT if that difference is small, then start from the tall end to search for the insertion place.