As we all learned in kindergarten, you can easily sort an array in $$$O(n^{2})$$$ using well-known algorithms such as bubble sort, insertion sort, and such.
We took inspiration from Stalin Sort (SS for short) and improved the upper bound from $$$O(n^{2})$$$ to $$$O(n\sqrt{n}log(n))$$$ with an algorithm that we called Hitler Sort (HS).
In this blog we will describe the algorithm and prove the upper bound on sorting, breaking the previously known bound of $$$O(n^{2})$$$.
The algorithm: We will use the well-known $$$O(nlogn)$$$ time LIS/LDS algorithm to find the LIS and LDS of the input array $$$A$$$ of length $$$n$$$, by the Erdős–Szekeres theorem, $$$max(LIS,LDS)\ge \sqrt{n}$$$ and therfore, if we erase the maximal monotonic subseqence $$$S$$$ from the array, we will be left with an array $$$A\S$$$ of size at most $$$n-\sqrt(n)$$$ that we will sort recursively, lastly we can merge $$$S$$$ and $$$A\S$$$ with the classic merge algorithm in $$$O(n)$$$ time.
We will now prove the time complexity of the algorithm. let us denote by $$$T(n)$$$ the running time of the Hitler-Sort algorithm. We notice that finding the LIS/LDS takes $$$O(nlogn)$$$ time, and that the merge operation takes $$$O(n)$$$ time, we further notice that we recursively sort an array of size at most $$$n-\sqrt{n}$$$. therefore we have $$$T(n)\le T(n-\sqrt{n}) + O(n) + O(nlogn) = T(n-\sqrt{n}) + O(nlogn)$$$. And therefore there exists some $$$c \gt 0$$$ such that for all $$$n$$$, $$$T(n) \le T(n-\sqrt{n})+cnlogn$$$. we will prove by induction that $$$T(n)\le cn\sqrt{n}logn$$$ for all $$$n$$$: $$$T(n)\le T(n-\sqrt{n})+cnlogn \le c(n-\sqrt{n})\sqrt{n-\sqrt{n}}log(n-\sqrt{n})+cnlogn \le c(n-\sqrt{n})\sqrt{n}logn+cnlogn = cn\sqrt{n}logn-c\sqrt{n}\sqrt{n}logn+cnlogn=cn\sqrt{n}logn$$$ $$$\implies$$$ $$$T(n)=O(n\sqrt{n}logn)$$$ $$$\blacksquare$$$
We will now prove that in the worst-case, $$$T(n)=\Theta (n\sqrt{n}log(n))$$$.
Consider the array $$$A=[\sqrt{n},\sqrt{n}-1,\dots,1,2\sqrt{n},2\sqrt{n}-1,\dots,\sqrt{n}+1,\dots,n,n-1,\dots,n-\sqrt{n}+1]$$$ has $$$n$$$ elements, and is composed of $$$\sqrt{n}$$$ decreasing chains of length $$$\sqrt{n}$$$, and it's LIS and LDS are both $$$\sqrt{n}$$$. We notice that if we remove the LDS (any of them) in each recursive call of Hitler_Sort, the LDS remains $$$\sqrt{n}$$$ and the LIS decreases. we notice that finding the LDS takes $$$\Theta(n_{i}log(n_{i}))$$$ time in each recursive call, and therefore there exists some $$$c \gt 0$$$ such that finding the LDS takes more then $$$cn_{i}log(n_{i})$$$ time in each recursive call. Therefore we get the running time of Hitler_Sort on the array A: $$$T(n) \ge T(n-\sqrt{n})+cnlog(n) \ge T(n-\sqrt{n}-\sqrt{n})+c(n-\sqrt{n})log(n-\sqrt{n})+cnlog(n)$$$ $$$= T(n-2\sqrt{n})+c(n-\sqrt{n})log(n-\sqrt{n})+cnlog(n)$$$ $$$\ge \dots \ge \displaystyle\sum_{k=0}^{\sqrt{n}}c(n-k\sqrt{n})log(n-k\sqrt{n})$$$ $\ge \displaystyle\sum_{k=0}^{\frac{\sqrt{n}}{2}}c(n-k\sqrt{n})log(n-k\sqrt{n}) \ge \displaystyle\sum_{k=0}^{\sqrt{n}/2}c(\frac{n}{2})log(\frac{n}{2})
