## 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 built-in 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: In-Place

Intuition

If we want to do the sort in-place, 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++ and j--.

• If it is (1, 0), we swap them so they are correct, then continue.

• If it is (0, 0), only the i place is correct, so we i++ and continue.

• If it is (1, 1), only the j place is correct, so we j-- and continue.

Throughout all 4 cases, the loop invariant is maintained, and j-i 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 makes j-i 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.