Решение задачи Ихаб и странный человек с Codeforces

Вам дан массив a длины n. Вы можете выполнить следующую операцию с ним столько раз, сколько захотите:

Выберите любые два числа i и j (1≤i,j≤n), такие что сумма ai+aj нечетная, и поменяйте местами ai и aj.
Какой лексикографически минимальный массив вы можете получить?

Массив x лексикографически меньше чем массив y, если есть такой индекс i, что xi

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, cnt[2], a[N];
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]), ++cnt[a[i] & 1];
	if (cnt[0] && cnt[1])
		sort(a, a + n);
	for (int i = 0; i < n; ++i)
		printf("%d ", a[i]);
}