A topology question arised from my sorting algorithm

Question

I made a new sorting algorithm. It's named Quick-Merge Sort. It is applicable to random-accessible containers. It goes:

1. Choose a pivot and start partitioning the container, like in Quick Sort. Do this while the "special condition" is satisfied.

   • When the "special condition" is violated, this interrupts the process.

2. If interruption didn't take place (that is, an iteration of Quick Sort is completed), recursively sort the sub-containers of the partition.

   • Otherwise, break the entire container in two, sort each of them recursively, and then merge the resulting runs, like in Merge Sort.

This arises the following topology question.

Give $ℝ^2$ the usual topology. Define subspaces $X$ and $C$ as follows:

$$ X = \{(x,y): x≥0 \land y≥0 \land x+y≤1\} $$ $$ C = \{(x,y):x+y=1\} $$ $C$ is called the line of completion.

Let $x$ be the proportion of entries that has been sorted below the pivot while Step 1, and let $y$ be the proportion of entries that has been sorted above the pivot while Step 1. Then $(x,y) \in X$.

The set $A$ of $(x,y)$ satisfying the "special condition" is called the region of Quick Sort. Since either $x$ or $y$ always increases during Step 1, $A$ is any subspace of $X$ that satisfies:

$$ \forall (x,y) \in A \quad \exists f:[0,1]\overset{\text{continuous}}{\to} A \quad \forall t \in [0,1] \quad f(0)=(0,0) \land f(1)=(x,y) \land (\pi_1 \circ f)^\prime(t)≥0 \land (\pi_2 \circ f)^\prime(t)≥0 $$

That is, for every point in $A$, there exists a path from the origin to the point whose derivative is either zero or toward right, up, or the 1st quadrant.

The "special condition" must reduce the worst-case time complexity to $O(n \log n)$. As a consequence, $A$ must also satisfy:

$$ \forall z \in [0,1] \quad A \cap \{(x,y):x+y=z\} \space \text{is nonempty and connected} \land \overline{A} \cap \{(0,1),(1,0)\} = \emptyset $$ Where the closure is defined in $X$.

Let $B$, the curve of interruption, be $\text{Bd} \space A$, where closure is defined in $\{(x,y):x≥0 \land y≥0\}$. The questions are:

• Is $B$ always path-connected?

• Is $B$ always connected?

• If any of the above is false, what would be a pathological example?

(Note that interruption doesn't take place when $(x,y) \in B \cap C$.)

Answer 1

From the "special condition", we can deduce:

$$ \exists g,h:[0,1] → [-1,1] \quad \forall u \in [0,1] \quad \overline{\{y-x:(x,y)\in A \land x+y=u\}}=[h(u),g(u)] $$

Let $u=x+y$ and $v=y-x$. From the other condition of $A$, we can deduce:

$$ \forall u_1,u_2 \in [0,1] \quad u_1 < u_2 → (\frac{g(u_2)-g(u_1)}{u_2-u_1}≤1 \land \frac{h(u_2)-h(u_1)}{u_2-u_1}≥-1) $$

Then $g(u)-u$ and $h(u)+u$ are monotone, and thus their discontinuities are jump discontinuities.

Then $B$ is the union of the graphs of $v=g(u)$ and $v=h(u)$ with their jump discontinuities and $g(1)$-to-$h(1)$ interpolated, then subtracting $\{(x,y):x=0 \lor y=0\}$ and then taking closure in $X$. It follows that $B$ is path-connected.