The algorithm in the question can be stated more clearly in the following form since considering the odd $i$ does not have any effect once $i-1$ has been take care of.
for even i from 0 to 2N-2:
if array[i] and array[i+1] does not constitute a pair:
find the pair for the i-th one and swap position with i+1 element
Here is an outline of the proof.
Given an array $A$ of size $2N$ with integers ranging from $0$ to $2N-1$, let us construct a graph $G$. Replacing $2i-1$ with $2(i-1)$ for all $i$, we will have a new array $B$ of even integers from $0$ to $2(N-1)$, each of which appears twice. Let $G$ have vertices $0, 2, \cdots, 2(N-2)$.
- If $B[0]=2i$ and $B[1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
- If $B[2]=2i$ and $B[3]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
- $\cdots$
- If $B[2N-2]=2i$ and $B[2N-1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
Please note since $2i$ might be the same as $2j$, $G$ may have self-loops. Since each even number appears twice in array $B$, the degree of each of vertices of $G$ is 2 (2-regular graph). That means $G$ is a disjoint union of cycles.
Define a function $s$ from arrays which are permutations of $0, 1, \cdots, 2N-1$ to $\Bbb N$, $s(A)=$ the number of cycles in $G$, where $G$ is obtained from $A$ by the above deterministic construction.
Claim (at most 1 increase with one swap). Suppose an array $A$ is changed to $A'$ by a swap of two elements. Then $s(A')\le s(A)+1$.
Suppose we have proved the claim. Notice that $s(A)=N$, the maximum value of $s$ if and only if all pairs are next to each other. Since you can only increase at most 1 to $s(A)$ by each swap and the greedy algorithm does increase $s(A)$ by 1 with each of its swaps, the greedy algorithm must be optimal.
I will leave the gaps in the above proof as two easy exercises.
Exercise 1: The greedy algorithm increase the value of $s$ by 1 with each of its swaps.
Exercise 2: Prove the claim of at most 1 increase with one swap.
