Typical implementations of quicksort don't append the pivot to one of the lists. Instead, they are implemented (in Haskell notation) as
qsort [] = []
qsort xs = qsort left ++ [pivot] ++ qsort right
where pivot = head xs
left = filter (<x) xs
right = filter (>=x) xs
which keeps the symmetry between the left and right lists (if the list elements are distinct) and results in the same number of comparisons for an initial list that is sorted increasing or sorted decreasing.
Note that the 'worst case' isn't just found for the lists that are sorted in increasing or decreasing order. For example, the following lists all require six comparisons to sort:
[1,2,3,4]
[1,2,4,3]
[1,4,2,3]
[1,4,3,2]
[4,3,2,1]
[4,3,1,2]
[4,1,2,3]
[4,1,3,2]
In general, any ordering which results in the lest or greatest element being selected as the pivot at every stage of the recursion will give you worst case performance.
If you want to make use of pre-sorted lists, the the idea is to use the fact that the median will be located at $i = floor(\frac{N}{2})$, where $N$ is the length of the list you're looking for.
The nice thing about splitting the list is that when we recurse, we can simply use the sub-lists from $[0, i)$ and $[i, N)$ to find the median again.
However, as you noticed, we need to be smart about splitting the two lists in the K-D tree. The general idea is if we pick a point $P = (x_0, y_0)$ to split with, we need to split both the $X$-sorted list with respect to $x_0$ and the $Y$ sorted list with respect to $x_0$. (We split both according to $x_0$, not one with $x_0$ and one with $y_0$)
In the given example,
0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)
When we split with the point 4 = (2, 1), the
$X$ list splits as: (it splits at $x_0 = 2$)
1 = (2, 9)
4 = (2, 1)
----------
3 = (3, 6)
0 = (4, 7)
2 = (5, 4)
Clearly, the two sub-lists are still sorted by $x$
the $Y$ list splits at $x_0 = 2$
4 = (2, 1)
1 = (2, 9)
----------
2 = (5, 4)
3 = (3, 6)
0 = (4, 7)
Notice that the two subsections of the $Y$ are still sorted with respect to the y coordinate, but they were split along the x coordinate.
Implementing this is exactly like implementing the reverse of the merge operation from merge sort.
Now that you have the $X$ and $Y$ sublists for the recursion, you can continue building the K-D tree.
Best Answer
You can do it by bisection. Let's take a longer array, $11,12,13,\dots 29,1,2,3,\dots 10$ If you pick an element $n$, if $n \ge 11$ the break is to the right of $n$ and if $n \le 10$ the break is to the left of $n$.