Статья подготовлена для студентов курса  «Алгоритмы для разработчиков» в образовательном проекте OTUS. Когда люди изучают алгоритмы сортировок, у них часто возникает вопрос: а существует ли идеальный алгоритм, который может сортировать всё за линейное время или даже быстрее — за константное? Ответ: не существует и не может существовать. Почему? Предположим, у нас есть n-элементов (вектор), которые нужно отсортировать: а1, а2, …, аn. Любой алгоритм сортировки из любого входного вектора делает отсортированный выходной вектор...

Идея сортировки Представим, что у нас есть неотсортированный массив A. Нам нужно его отсортировать по неубыванию. Давайте будем рассматривать поочерёдно каждый элемент массива, начиная со второго элемента(под индексом 1), и заканчивая последним элементом массива A. Процесс "рассмотрения" элемента будет выглядеть следующим образом: 1)Мы знаем, что слева от рассматриваемого нами элемента...