Информатика программа

Сортировка c предварительным выбором. Из массива путем однократного

просмотра выбирается последовательность элементов, находящихся в порядке

возрастания и переносится очередную строку двумерного массива с заменой во

входном на -1. Этот процесс повторяется, пока в массиве не останется

возрастающих последовательностей. После этого в массиве остается

последовательность в порядке убывания, которая также заносится в строку

массива «задом наперед». Затем для строк производится однократное слияние. 

Если строки в двумерном массиве окончатся раньше, после слияния оставшиеся

элементы добавляются в выходной массив при помощи погружения.

Алгоритм сортировки реализовать в виде функции, возвращающей в качестве

результата характеристику трудоемкости алгоритма (например, количество сравнений). 

Для получить трудоемкость для различных значений N=1000,5000,10000. Сравнить с

теоретической оценкой.