Мне дали этот алгоритм, который берет максимальный элемент (назовем его m) в массиве A и разбивает его так, чтобы все элементы, меньшие чем m, входили в набор A1, а все те, которые больше или равны, переходили в A2 , В конце концов, он работает рекурсивно на A1 и использует InsertionSort на A2. Он заканчивается после объединения A1 и A2 в A.
Прежде всего, я не совсем понимаю, почему он использует inserttionSort для A2 (я имею в виду, m - это максимум, поэтому A2 будет содержать только элементы, равные максимуму). В любом случае, один из вопросов касается поиска сценариев наихудшего и наилучшего вариантов и сложности их времени. Что касается сложности времени наихудшего случая, я думаю, что это O (n ^ 2), но я не совсем уверен (это должно быть похоже на SelectionSort, верно?) Что касается остального, я действительно не знаю ..