Since you have both lists, even if not both at the same time, your
space cost is at least that of the longest, thus at least $n/2$.
This corresponds to a $O(n)$ space complexity.
So, unless you exclude it for some reason, it makes sense to use a bit
array $M[1:n]$ to represent the set A by its characteristic function,
i.e. $M[i]=0$ iff $i\notin A$, and $1$ otherwise. The space complexity
is unchanged, and the array $M$ is actually much smaller than one of
the two lists (initial or final).
Initializing the array $M$ from the initial list is linear.
Then you can take the logical complement of the array $M$ in linear
Then you scan the array in linear time to get all the element of the
complement of your initial list in linear time $O(n)$
Of course, by now you have noticed your mistake: sorting is in time
$O(n \log n)$ (or better according to comment) when $n$ is the number
of element to be sorted. But it is trivially linear if $n$ is the size of the
finite ordered set they come from.
Using an array, as I just did is one way of sorting in linear time with respect to the size of the referance set.
Your own answer was good because of that. Only your complexity assessment was wrong.