Nearly Sorted Data

What is Insertion Sort?

Insertion sort builds the final sorted array one element at a time by taking each new element and shifting it leftward past every larger already-sorted element…