На самом деле решение этой задачи не может иметь линейную сложность. Алгоритмическая сложность для этой задачи ограничивается используемым алгоритмом сортировки, поэтому в лучшем случае можно придумать решение со сложностью O(n log n) — такова сложность алгоритма встроенной сортировки в JavaScript. Однако вами правильно было подмечено, что из-за использования метода shift предельная сложность алгоритма возрастает, что нельзя сказать для решений с использованием pop, как у меня, например.

т.к. дважды считаем x % 2

Так эта операция O(1), так что не вижу в этом ничего плохого + они считаются в разных контекстах, автор конечно мог быть сохранить результаты вычислений в hash map, но в данном случае это стоило бы гораздо дороже, чем просто повторно произвести вычисление

То, что меня напрягает в этом решении — это то, что оно O(n^2) из-за того, что внутри .map используется .shift, хотя задача спокойно решается за O(n)

а мне не очень нравится т.к. дважды считаем x % 2