Как отсортировать элементы так, чтобы слева находились нечетные элементы, а справа — четные?
Прочитайте про битовые операции. Если коротко, у нечетного числа в бинарном представлении последний бит всегда 1, например 3 это 11, 5 это 101  и тд.
2017 год. Вам не нужны std::binary_function и прочая устаревшая фигня. Да и можно заюзать лямбду, если этот компаратор нужен только в одном месте кода.
Судя по описанию задачи, Вам нужно не отсортировать массив -- Вам нужно сделать partition.
Воспользуйтесь стандартными алгоритмами std::partition (если относительный порядок чётных и нечётных элементов между собой не важен) или std::stable_partition (если нужно сохранить оригинальный порядок).
Пример:std::stable_partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 1; });