insertion sort

RU: сортировка вставкой

A comparison-based sorting algorithm that builds the sorted result one element at a time by shifting each new element leftward into its correct position among already-sorted elements. Time is O(n²) average and worst case; O(n) best case on nearly sorted input. It is stable, in-place, and preferred over faster algorithms for very small arrays.