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))$$$.
Notice the array $$$[\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.
