Solution
Approach 1: Sort
Intuition and Algorithm
Use a custom comparator when sorting, to sort by parity.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: for the sort, depending on the builtin implementation of
sort
.
Approach 2: Two Pass
Intuition and Algorithm
Write all the even elements first, then write all the odd elements.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: , the space used by the answer.
Approach 3: InPlace
Intuition
If we want to do the sort inplace, we can use quicksort, a standard textbook algorithm.
Algorithm
We'll maintain two pointers i
and j
. The loop invariant is everything below i
has parity 0
(ie. A[k] % 2 == 0
when k < i
), and everything above j
has parity 1
.
Then, there are 4 cases for (A[i] % 2, A[j] % 2)
:

If it is
(0, 1)
, then everything is correct:i++
andj
. 
If it is
(1, 0)
, we swap them so they are correct, then continue. 
If it is
(0, 0)
, only thei
place is correct, so wei++
and continue. 
If it is
(1, 1)
, only thej
place is correct, so wej
and continue.
Throughout all 4 cases, the loop invariant is maintained, and ji
is getting smaller. So eventually we will be done with the array sorted as desired.
Complexity Analysis

Time Complexity: , where is the length of
A
. Each step of the while loop makesji
decrease by at least one. (Note that while quicksort is normally, this is because we only need one pass to sort the elements.) 
Space Complexity: in additional space complexity.
Analysis written by: @awice.