Editorial

Спершу навчимося розв'язувати підзадачу 4 (там, де половина одиниць, половина двійок). Для цього розділимо наш масив на дві рівні половини. Розглянемо останній елемент першої половини. Якщо це двійка, то вона має стояти в другій половині, а тому ми беремо останній ($n$-ий) елемент і переміщуємо його на початок. При цьому останній елемент першого блоку переміститься на першу позицію правого блоку, тобто кількість двійок у другому блоці не зменшиться (може залишитись такою самою, як і до цього, за рахунок останнього елемента, який ми перемістили на першу позицію). Якщо ж так сталося, що останній елемент першого блоку "— одиниця, то ми просто переміщуємо його на початок. Так продовжуємо до моменту, коли ліворуч стоять усі одиниці, а праворуч двійки. Слід зазначити, що цей процес скінченний, більше того - використає $O(n)$ операцій. Доведення цього факту досить тривіальне, тому залишаємо його як вправу для читача.

Тепер повернемося до основної задачі. Розберемося з випадком, коли всі числа різні. Очевидним чином ми можемо відсортувати масив із двох елементів, що стоять на позиціях $1$ та $2$ (якщо перший елемент більший, ніж другий, "— переміщуємо другий на перше місце, інакше нічого не робимо).

Припустимо, що ми знаємо, як відсортувати масив розміру $n$ (елементи якого стоять на індексах $1\dots n$). Давайте навчимося сортувати масив розміру $2n$ (який розміщений також на індексах $1\dots 2n)$. Для початку визначимо, які елементи мають бути у лівій частині (тобто у межах індексів $1-n$), а які мають розміщуватися праворуч. Позначимо «ліві» елементи як одинички, «праві» як двійки. Наприклад, елементи масиву $[1,8,6,4,7,3,5,2]$ матимуть відповідно позначки $[1,2,2,1,2,1,2,1]$. Тепер слід перемістити ліворуч числа, що помічені одиничками, а праворуч числа, що помічені двійками. Робити це ми навчилися за допомогою четвертої підзадачі. Все, що залишилось, "— відсортувати дві половини. Для цього спершу відсортуємо ліву частину (робити це ми вміємо за припущенням), після цього $n$ разів перемістимо числа з кінця в початок (по суті, обмінявши ліву половину з правою), знову відсортуємо ліву половину (хоча там зараз записані елементи, що стоять праворуч), після чого знову $n$ разів перемістимо останній елемент масиву в початок, що дасть нам відсортований масив. Таким чином, ми вміємо для будь-якого $n$ сортувати масив за кількість операцій переміщення, що оцінюється як $O(n\log n)$.

Останній блок (коли числа можуть бути однаковими) можна перетворити в передостанній (коли числа не повторюються). Варіацій, як це зробити, дуже багато, але найпростіший спосіб "— домножити усі числа на $1000$ і додати номер позиції.

Оцінимо складність. Кількість виконаних операцій переміщення: $O(n\log n)$ (виходячи з майстер-методу, англ. Master theorem). Часова складність оптимального розв'язку: $O(n\log n)$ (але час дозволяє використати значно більшу кількість операцій). Складність щодо пам'яті: $O(n)$.