Чем отличается сортировка вставками от других алгоритмов сортировки, например, от быстрой сортировки?

Сортировка вставками и быстрая сортировка имеют свои особенности и отличия.

Сортировка вставками делит массив на две части: отсортированную и общую 1. В начале выполнения алгоритма считается, что первый элемент массива уже стоит на своём месте 1. Поэтому массив начинают рассматривать со второго элемента и продолжают так до тех пор, пока все элементы в отсортированной части не окажутся на своих местах 1.

Быстрая сортировка построена на принципе «Разделяй и властвуй» 13. В начале выполнения быстрой сортировки необходимо выбрать опорный элемент 1. Чаще всего это один из крайних элементов, но можно сделать выбор случайным образом 1. После этого массив делится на две части: элементы меньше «опоры» перемещаются влево, а больше — вправо 1. Далее рекурсивно выполняется деление и сортировка для каждой части до тех пор, пока части не достигнут минимального размера 1.

Таким образом, основное отличие в том, что сортировка вставками работает с элементами по одному, вставляя их в подходящее место среди ранее упорядоченных элементов, в то время как быстрая сортировка разделяет массив на две части по разные стороны от опорного элемента: элементы меньше опорного помещаются перед ним, а равные или большие — позади 3.