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](https://codeforces.me/problemset/problem/2027/B) (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](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html) to find the LIS and LDS of the input array $A$ of length $n$, by the [Erdős–Szekeres theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_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){n}$ that we will sort recursively, lastly we can merge $S$ and $A\\S$ with the classic merge algorithm in $O(n)$ time.↵
↵
<spoiler summary="C++ Code">↵
```c++↵
#include<bits/stdc++.h>↵
using namespace std;↵
void hitler_sort(vector<int>&vec){↵
if(vec.empty())return;↵
int n=vec.size();↵
vector<int> prev1(n,-1);↵
vector<int> prev2(n,-1);↵
vector<pair<int,int>> inc(n,{2e9,0});↵
vector<pair<int,int>> dec(n,{2e9,0});↵
int LIS=0,LDS=0;↵
for(int i=0;i<n;i++){↵
int ind=upper_bound(inc.begin(),inc.end(),pair<int,int>{vec[i],2e9+1})-inc.begin()-1;↵
if(ind!=-1)prev1[i]=inc[ind].second;↵
inc[ind+1]={vec[i],i};↵
LIS=max(LIS,ind+2);↵
ind=upper_bound(dec.begin(),dec.end(),pair<int,int>{-vec[i],2e9+1})-dec.begin()-1;↵
if(ind!=-1)prev2[i]=dec[ind].second;↵
dec[ind+1]={-vec[i],i};↵
LDS=max(LDS,ind+2);↵
}↵
vector<int> mono(LIS),is_mono(n,0);↵
if(LIS>LDS){↵
int curr=inc[LIS-1].second;↵
for(int i=0;i<LIS;i++){↵
mono[LIS-i-1]=vec[curr];↵
is_mono[curr]=1;↵
curr=prev1[curr];↵
}↵
mono.push_back(2e9);↵
}↵
else{↵
int curr=dec[LDS-1].second;↵
for(int i=0;i<LDS;i++){↵
mono[i]=vec[curr];↵
is_mono[curr]=1;↵
curr=prev2[curr];↵
}↵
mono.push_back(2e9);↵
}↵
vector<int> left;↵
for(int i=0;i<n;i++){↵
if(!is_mono[i])left.push_back(vec[i]);↵
}↵
hitler_sort(left);↵
int left_counter=0,mono_counter=0;↵
for(int i=0;i<n;i++){↵
if(left_counter!=left.size()&&left[left_counter]<mono[mono_counter])vec[i]=left[left_counter++];↵
else vec[i]=mono[mono_counter++];↵
} ↵
}↵
int main(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for(int &i:v)cin>>i;↵
hitler_sort(v);↵
for(int&i:v)cout << i <<" ";↵
return 0;↵
}```↵
</spoiler>↵
↵
↵
<spoiler summary="Python Code">↵
```python↵
from bisect import bisect_right ↵
def LIS_LDS(arr):↵
n=len(arr)↵
lis=1↵
lds=1↵
lis_dp=[(2e9,-1)]*n↵
lds_dp=[(2e9,-1)]*n↵
prev_lis=[-1]*n↵
prev_lds=[-1]*n↵
for i in range(0,n):↵
index=bisect_right(lis_dp,(arr[i],0),0,lis)-1↵
if(index!=-1):↵
prev_lis[i]=lis_dp[index][1]↵
lis_dp[index+1]=(arr[i],i)↵
lis=max(lis,index+2)↵
index=bisect_right(lds_dp,(-arr[i],0),0,lis)-1↵
if(index!=-1):↵
prev_lds[i]=lds_dp[index][1]↵
lds_dp[index+1]=(-arr[i],i)↵
lds=max(lds,index+2)↵
result=[0]*(max(lis,lds)) #the sequence in increasing order↵
indexes=[0]*n #1 if index is in sequence↵
if(lds<lis):↵
curr=lis_dp[lis-1][1]↵
for i in range(0,lis):↵
result[lis-i-1]=arr[curr];↵
indexes[curr]=1;↵
curr=prev_lis[curr];↵
else:↵
curr=lds_dp[lds-1][1]↵
for i in range(0,lds):↵
result[i]=arr[curr];↵
indexes[curr]=1;↵
curr=prev_lds[curr];↵
return (result,indexes)↵
↵
↵
def merge(arr_1,arr_2,dest):↵
count_1=0↵
count_2=0↵
ind = 0↵
↵
while count_1 < len(arr_1) and count_2 < len(arr_2):↵
if arr_1[count_1] < arr_2[count_2]:↵
dest[ind] = arr_1[count_1]↵
ind += 1↵
count_1 += 1↵
else:↵
dest[ind] = arr_2[count_2]↵
ind += 1↵
count_2 += 1↵
while count_1 < len(arr_1):↵
dest[ind] = arr_1[count_1]↵
ind += 1↵
count_1 += 1↵
while count_2 < len(arr_2):↵
dest[ind] = arr_2[count_2]↵
ind += 1↵
count_2 += 1↵
↵
↵
def hitler_sort(arr):↵
n=len(arr)↵
if(n==0):↵
return None↵
(monotone,indexes)=LIS_LDS(arr)↵
other =[]↵
for i in range(0,n):↵
if(not indexes[i]):↵
other.append(arr[i])↵
hitler_sort(other)↵
merge(other,monotone,arr)↵
↵
def main():↵
n=int(input())↵
arr = [int(x) for x in input().split(' ')]↵
hitler_sort(arr)↵
print(arr)↵
↵
if __name__ == '__main__':↵
main()↵
```↵
</spoiler>↵
↵
↵
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>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)$↵
↵
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>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}^{\frac{\sqrt{n}}{2}}c(\frac{n}{2})log(\frac{n}{2})$ $=c\frac{\sqrt{n}}{2}\frac{n}{2}log(\frac{n}{2})$ $=\frac{c}{4}(n\sqrt{n}log(n)-n\sqrt{n})$ ↵
$\ge \frac{c}{8}(n\sqrt{n}log(n)) = \Theta(n\sqrt{n}log(n)$ ↵
↵
We proved an upper and lower bound of $cn\sqrt{n}log(n)$ on the running time of Hitler_Sort on the array $A$, proving that Hitler_Sort runs in $\Theta(n\sqrt{n}log(n))$ time worst-case.↵
↵
In the best-case, on sorted or reversed arrays, Hitler_Sort runs in $\Theta(nlog(n))$ time and immediately stops. ↵
↵
The average-case analysis is very similar to the worst-case analysis using the fact that the expected value of $max(LDS,LIS)$ is $2\sqrt{n}(1+o(1))$, resulting in an expected runtime of $\Theta(n\sqrt{n}log(n))$.↵
↵
We managed to improve the prevoiusly known bound of sorting in a comparison-based model from $O(n^{2})$ to $O(n\sqrt{n}log(n))$ in the worst case, and it remains an open problem whether this bound can be improved further.↵
↵
Thank you for reading this far, we hope you enjoyed this blog and would love to hear comments and ideas.↵
↵
danke und auf Wiedersehen!↵
↵
↵
We took inspiration from [Stalin Sort](https://codeforces.me/problemset/problem/2027/B) (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](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html) to find the LIS and LDS of the input array $A$ of length $n$, by the [Erdős–Szekeres theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_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
↵
<spoiler summary="C++ Code">↵
```c++↵
#include<bits/stdc++.h>↵
using namespace std;↵
void hitler_sort(vector<int>&vec){↵
if(vec.empty())return;↵
int n=vec.size();↵
vector<int> prev1(n,-1);↵
vector<int> prev2(n,-1);↵
vector<pair<int,int>> inc(n,{2e9,0});↵
vector<pair<int,int>> dec(n,{2e9,0});↵
int LIS=0,LDS=0;↵
for(int i=0;i<n;i++){↵
int ind=upper_bound(inc.begin(),inc.end(),pair<int,int>{vec[i],2e9+1})-inc.begin()-1;↵
if(ind!=-1)prev1[i]=inc[ind].second;↵
inc[ind+1]={vec[i],i};↵
LIS=max(LIS,ind+2);↵
ind=upper_bound(dec.begin(),dec.end(),pair<int,int>{-vec[i],2e9+1})-dec.begin()-1;↵
if(ind!=-1)prev2[i]=dec[ind].second;↵
dec[ind+1]={-vec[i],i};↵
LDS=max(LDS,ind+2);↵
}↵
vector<int> mono(LIS),is_mono(n,0);↵
if(LIS>LDS){↵
int curr=inc[LIS-1].second;↵
for(int i=0;i<LIS;i++){↵
mono[LIS-i-1]=vec[curr];↵
is_mono[curr]=1;↵
curr=prev1[curr];↵
}↵
mono.push_back(2e9);↵
}↵
else{↵
int curr=dec[LDS-1].second;↵
for(int i=0;i<LDS;i++){↵
mono[i]=vec[curr];↵
is_mono[curr]=1;↵
curr=prev2[curr];↵
}↵
mono.push_back(2e9);↵
}↵
vector<int> left;↵
for(int i=0;i<n;i++){↵
if(!is_mono[i])left.push_back(vec[i]);↵
}↵
hitler_sort(left);↵
int left_counter=0,mono_counter=0;↵
for(int i=0;i<n;i++){↵
if(left_counter!=left.size()&&left[left_counter]<mono[mono_counter])vec[i]=left[left_counter++];↵
else vec[i]=mono[mono_counter++];↵
} ↵
}↵
int main(){↵
int n;cin>>n;↵
vector<int> v(n);↵
for(int &i:v)cin>>i;↵
hitler_sort(v);↵
for(int&i:v)cout << i <<" ";↵
return 0;↵
}```↵
</spoiler>↵
↵
↵
<spoiler summary="Python Code">↵
```python↵
from bisect import bisect_right ↵
def LIS_LDS(arr):↵
n=len(arr)↵
lis=1↵
lds=1↵
lis_dp=[(2e9,-1)]*n↵
lds_dp=[(2e9,-1)]*n↵
prev_lis=[-1]*n↵
prev_lds=[-1]*n↵
for i in range(0,n):↵
index=bisect_right(lis_dp,(arr[i],0),0,lis)-1↵
if(index!=-1):↵
prev_lis[i]=lis_dp[index][1]↵
lis_dp[index+1]=(arr[i],i)↵
lis=max(lis,index+2)↵
index=bisect_right(lds_dp,(-arr[i],0),0,lis)-1↵
if(index!=-1):↵
prev_lds[i]=lds_dp[index][1]↵
lds_dp[index+1]=(-arr[i],i)↵
lds=max(lds,index+2)↵
result=[0]*(max(lis,lds)) #the sequence in increasing order↵
indexes=[0]*n #1 if index is in sequence↵
if(lds<lis):↵
curr=lis_dp[lis-1][1]↵
for i in range(0,lis):↵
result[lis-i-1]=arr[curr];↵
indexes[curr]=1;↵
curr=prev_lis[curr];↵
else:↵
curr=lds_dp[lds-1][1]↵
for i in range(0,lds):↵
result[i]=arr[curr];↵
indexes[curr]=1;↵
curr=prev_lds[curr];↵
return (result,indexes)↵
↵
↵
def merge(arr_1,arr_2,dest):↵
count_1=0↵
count_2=0↵
ind = 0↵
↵
while count_1 < len(arr_1) and count_2 < len(arr_2):↵
if arr_1[count_1] < arr_2[count_2]:↵
dest[ind] = arr_1[count_1]↵
ind += 1↵
count_1 += 1↵
else:↵
dest[ind] = arr_2[count_2]↵
ind += 1↵
count_2 += 1↵
while count_1 < len(arr_1):↵
dest[ind] = arr_1[count_1]↵
ind += 1↵
count_1 += 1↵
while count_2 < len(arr_2):↵
dest[ind] = arr_2[count_2]↵
ind += 1↵
count_2 += 1↵
↵
↵
def hitler_sort(arr):↵
n=len(arr)↵
if(n==0):↵
return None↵
(monotone,indexes)=LIS_LDS(arr)↵
other =[]↵
for i in range(0,n):↵
if(not indexes[i]):↵
other.append(arr[i])↵
hitler_sort(other)↵
merge(other,monotone,arr)↵
↵
def main():↵
n=int(input())↵
arr = [int(x) for x in input().split(' ')]↵
hitler_sort(arr)↵
print(arr)↵
↵
if __name__ == '__main__':↵
main()↵
```↵
</spoiler>↵
↵
↵
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>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)$↵
↵
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>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}^{\frac{\sqrt{n}}{2}}c(\frac{n}{2})log(\frac{n}{2})$ $=c\frac{\sqrt{n}}{2}\frac{n}{2}log(\frac{n}{2})$ $=\frac{c}{4}(n\sqrt{n}log(n)-n\sqrt{n})$ ↵
$\ge \frac{c}{8}(n\sqrt{n}log(n)) = \Theta(n\sqrt{n}log(n)$ ↵
↵
We proved an upper and lower bound of $cn\sqrt{n}log(n)$ on the running time of Hitler_Sort on the array $A$, proving that Hitler_Sort runs in $\Theta(n\sqrt{n}log(n))$ time worst-case.↵
↵
In the best-case, on sorted or reversed arrays, Hitler_Sort runs in $\Theta(nlog(n))$ time and immediately stops. ↵
↵
The average-case analysis is very similar to the worst-case analysis using the fact that the expected value of $max(LDS,LIS)$ is $2\sqrt{n}(1+o(1))$, resulting in an expected runtime of $\Theta(n\sqrt{n}log(n))$.↵
↵
We managed to improve the prevoiusly known bound of sorting in a comparison-based model from $O(n^{2})$ to $O(n\sqrt{n}log(n))$ in the worst case, and it remains an open problem whether this bound can be improved further.↵
↵
Thank you for reading this far, we hope you enjoyed this blog and would love to hear comments and ideas.↵
↵
danke und auf Wiedersehen!↵
↵
