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)$ 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 (Nazi version)">↵
```c++↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define RACE_THEORY true↵
#define HITLER 2e9//Hitler is the sigma↵
void hitler_sort(vector<int>&germany){//the final solution for sorting in O(n√nlogn)↵
if(germany.empty())return;//we cleaned europe from the jews↵
int n=germany.size();↵
// get the largest amount of aryans (lis)↵
vector<int> prev1(n,-1);↵
vector<int> prev2(n,-1);↵
vector<pair<int,int>> ss(n,{2e9,0});↵
vector<pair<int,int>> gestapo(n,{2e9,0});↵
int LIS=0,LDS=0;↵
for(int i=0;i<n;i++){↵
int fellow_nazi=upper_bound(ss.begin(),ss.end(),pair<int,int>{germany[i],2e9+1})-ss.begin()-1;↵
if(fellow_nazi!=-1)prev1[i]=ss[fellow_nazi].second;↵
ss[fellow_nazi+1]={germany[i],i};↵
LIS=max(LIS,fellow_nazi+2);↵
fellow_nazi=upper_bound(gestapo.begin(),gestapo.end(),pair<int,int>{-germany[i],2e9+1})-gestapo.begin()-1;↵
if(fellow_nazi!=-1)prev2[i]=gestapo[fellow_nazi].second;↵
gestapo[fellow_nazi+1]={-germany[i],i};↵
LDS=max(LDS,fellow_nazi+2);↵
}↵
// building a strong aryan base to rule the world↵
vector<int> aryans(LIS),is_aryan(n,0);↵
if(LIS>LDS){↵
int curr_aryan=ss[LIS-1].second;↵
for(int i=0;i<LIS;i++){↵
aryans[LIS-i-1]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev1[curr_aryan];↵
}↵
aryans.push_back(HITLER);↵
}↵
else{↵
int curr_aryan=gestapo[LDS-1].second;↵
for(int i=0;i<LDS;i++){↵
aryans[i]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev2[curr_aryan];↵
}↵
aryans.push_back(HITLER);↵
}↵
// gathering the jews↵
vector<int> jews;↵
for(int i=0;i<n;i++){↵
if(!is_aryan[i])jews.push_back(germany[i]);↵
}↵
hitler_sort(jews);//get the jews in order↵
// merge west germany and east germany↵
int jew_counter=0/*need to get that up to 6e6*/,nazi_counter=0/*need to get that up to the whole world*/;↵
for(int i=0;i<n;i++){↵
if(jew_counter!=jews.size()&&jews[jew_counter]<aryans[nazi_counter])germany[i]=jews[jew_counter++];↵
else germany[i]=aryans[nazi_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="C++ Code (clean version)">↵
```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 (clean)">↵
```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>↵
↵
↵
<spoiler summary="C Code (Nazi version & optimized for time)">↵
```c↵
#include<stdio.h>↵
#include<stdlib.h>↵
#define RACE_THEORY 1↵
#define HITLER 2e9 //Hitler is the sigma↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("avx2")↵
int prev1[200000];↵
int prev2[200000];↵
int ss[200000][2];↵
int gestapo[200000][2];↵
int is_aryan[200000];↵
int LIS=0,LDS=0,jew_index=0,fellow_nazi=0,count,step,index;↵
inline int nazi_bound(int arr[200000][2],int n, int val){↵
count=n,index=0;↵
while(count>0){↵
step=count/2;↵
if(val>=arr[index+step][0]){↵
index+=step+1;↵
count-=step+1;↵
}↵
else{↵
count=step;↵
}↵
}↵
return index-1;↵
}↵
int max(int a, int b){↵
return (a>b)*a+(a<=b)*b;↵
}↵
void hitler_sort(int* germany,int n){//the final solution for sorting in O(n√nlogn)↵
if(n==0)return;//we cleaned europe from the jews↵
// get the largest amount of aryans (lis,lds)↵
for(int i=0;i<n;i++)gestapo[i][0]=ss[i][0]=2e9,gestapo[i][1]=ss[i][1]=0;↵
LIS=LDS=0;↵
for(int i=0;i<n;i++){↵
fellow_nazi=nazi_bound(ss,LIS+1,germany[i]);↵
if(fellow_nazi!=-1)prev1[i]=ss[fellow_nazi][1];↵
ss[fellow_nazi+1][0]=germany[i],ss[fellow_nazi+1][1]=i;↵
LIS=max(LIS,fellow_nazi+2);↵
fellow_nazi=nazi_bound(gestapo,LDS+1,-germany[i]);↵
if(fellow_nazi!=-1)prev2[i]=gestapo[fellow_nazi][1];↵
gestapo[fellow_nazi+1][0]=-germany[i],gestapo[fellow_nazi+1][1]=i;↵
LDS=max(LDS,fellow_nazi+2);↵
}↵
// building a strong aryan base to rule the world↵
int* aryans=(int*)malloc((max(LIS,LDS)+1)*sizeof(int));↵
for(int i=0;i<n;i++)is_aryan[i]=0;↵
if(LIS>LDS){↵
int curr_aryan=ss[LIS-1][1];↵
for(int i=0;i<LIS;i++){↵
aryans[LIS-i-1]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev1[curr_aryan];↵
}↵
aryans[LIS]=HITLER;↵
}↵
else{↵
int curr_aryan=gestapo[LDS-1][1];↵
for(int i=0;i<LDS;i++){↵
aryans[i]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev2[curr_aryan];↵
}↵
aryans[LDS]=HITLER;↵
}↵
// gathering the jews↵
int* jews=(int*)malloc((n-max(LIS,LDS))*sizeof(int));↵
int jew_nose_size=n-max(LIS,LDS);↵
jew_index=0;↵
for(int i=0;i<n;i++){↵
if(!is_aryan[i])jews[jew_index++]=germany[i];↵
}↵
hitler_sort(jews,n-max(LDS,LIS));//get the jews in order↵
// merge west germany and east germany↵
int jew_counter=0/*need to get that up to 6e6*/,nazi_counter=0/*need to get that up to the whole world*/;↵
for(int i=0;i<n;i++){↵
if(jew_counter!=jew_nose_size&&jews[jew_counter]<aryans[nazi_counter])germany[i]=jews[jew_counter++];↵
else germany[i]=aryans[nazi_counter++];↵
}↵
free(aryans);↵
//we do not free(jews);↵
}↵
int main(){↵
int n;scanf("%d",&n);↵
int* v=(int*)malloc(n*sizeof(int));↵
for(int i=0;i<n;i++){↵
scanf("%d",v+i);↵
}↵
hitler_sort(v,n);↵
for(int i=0;i<n;i++){↵
printf("%d ",v[i]);↵
}↵
free(v);↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Story behind the algorithm (Nazi)">↵
the theory: kill the jews!↵
we propose the following sorting method:↵
we will call a monotone sequence an aryan sequence, and we will fix germany such that it will be aryan.↵
by the Erdős–Szekeres theorem we know that there is an aryan subsequence of length at least √n, will can find it using well known LIS finding algorithms.↵
after we found the aryan subsequence we will build two new arrays, one will be the aryan subsequence, and the other will be the jews.↵
next, we propose that germany will fix the damn jews and get them back in order, so we recursivly sort the jews.↵
now that we have the aryans and the sorted jews, we will reverse the aryans if they are decreasing and then we will merge the aryans and sorted jews to get a united germany.↵
the time until we finish the war is ↵
$T(n)=O(nlogn)+T(n-√n) \implies T(n)=O(n√nlogn)$↵
</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)$ $\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>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(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 (Nazi version)">↵
```c++↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define RACE_THEORY true↵
#define HITLER 2e9//Hitler is the sigma↵
void hitler_sort(vector<int>&germany){//the final solution for sorting in O(n√nlogn)↵
if(germany.empty())return;//we cleaned europe from the jews↵
int n=germany.size();↵
// get the largest amount of aryans (lis)↵
vector<int> prev1(n,-1);↵
vector<int> prev2(n,-1);↵
vector<pair<int,int>> ss(n,{2e9,0});↵
vector<pair<int,int>> gestapo(n,{2e9,0});↵
int LIS=0,LDS=0;↵
for(int i=0;i<n;i++){↵
int fellow_nazi=upper_bound(ss.begin(),ss.end(),pair<int,int>{germany[i],2e9+1})-ss.begin()-1;↵
if(fellow_nazi!=-1)prev1[i]=ss[fellow_nazi].second;↵
ss[fellow_nazi+1]={germany[i],i};↵
LIS=max(LIS,fellow_nazi+2);↵
fellow_nazi=upper_bound(gestapo.begin(),gestapo.end(),pair<int,int>{-germany[i],2e9+1})-gestapo.begin()-1;↵
if(fellow_nazi!=-1)prev2[i]=gestapo[fellow_nazi].second;↵
gestapo[fellow_nazi+1]={-germany[i],i};↵
LDS=max(LDS,fellow_nazi+2);↵
}↵
// building a strong aryan base to rule the world↵
vector<int> aryans(LIS),is_aryan(n,0);↵
if(LIS>LDS){↵
int curr_aryan=ss[LIS-1].second;↵
for(int i=0;i<LIS;i++){↵
aryans[LIS-i-1]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev1[curr_aryan];↵
}↵
aryans.push_back(HITLER);↵
}↵
else{↵
int curr_aryan=gestapo[LDS-1].second;↵
for(int i=0;i<LDS;i++){↵
aryans[i]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev2[curr_aryan];↵
}↵
aryans.push_back(HITLER);↵
}↵
// gathering the jews↵
vector<int> jews;↵
for(int i=0;i<n;i++){↵
if(!is_aryan[i])jews.push_back(germany[i]);↵
}↵
hitler_sort(jews);//get the jews in order↵
// merge west germany and east germany↵
int jew_counter=0/*need to get that up to 6e6*/,nazi_counter=0/*need to get that up to the whole world*/;↵
for(int i=0;i<n;i++){↵
if(jew_counter!=jews.size()&&jews[jew_counter]<aryans[nazi_counter])germany[i]=jews[jew_counter++];↵
else germany[i]=aryans[nazi_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="C++ Code (clean version)">↵
```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 (clean)">↵
```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>↵
↵
↵
<spoiler summary="C Code (Nazi version & optimized for time)">↵
```c↵
#include<stdio.h>↵
#include<stdlib.h>↵
#define RACE_THEORY 1↵
#define HITLER 2e9 //Hitler is the sigma↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("avx2")↵
int prev1[200000];↵
int prev2[200000];↵
int ss[200000][2];↵
int gestapo[200000][2];↵
int is_aryan[200000];↵
int LIS=0,LDS=0,jew_index=0,fellow_nazi=0,count,step,index;↵
inline int nazi_bound(int arr[200000][2],int n, int val){↵
count=n,index=0;↵
while(count>0){↵
step=count/2;↵
if(val>=arr[index+step][0]){↵
index+=step+1;↵
count-=step+1;↵
}↵
else{↵
count=step;↵
}↵
}↵
return index-1;↵
}↵
int max(int a, int b){↵
return (a>b)*a+(a<=b)*b;↵
}↵
void hitler_sort(int* germany,int n){//the final solution for sorting in O(n√nlogn)↵
if(n==0)return;//we cleaned europe from the jews↵
// get the largest amount of aryans (lis,lds)↵
for(int i=0;i<n;i++)gestapo[i][0]=ss[i][0]=2e9,gestapo[i][1]=ss[i][1]=0;↵
LIS=LDS=0;↵
for(int i=0;i<n;i++){↵
fellow_nazi=nazi_bound(ss,LIS+1,germany[i]);↵
if(fellow_nazi!=-1)prev1[i]=ss[fellow_nazi][1];↵
ss[fellow_nazi+1][0]=germany[i],ss[fellow_nazi+1][1]=i;↵
LIS=max(LIS,fellow_nazi+2);↵
fellow_nazi=nazi_bound(gestapo,LDS+1,-germany[i]);↵
if(fellow_nazi!=-1)prev2[i]=gestapo[fellow_nazi][1];↵
gestapo[fellow_nazi+1][0]=-germany[i],gestapo[fellow_nazi+1][1]=i;↵
LDS=max(LDS,fellow_nazi+2);↵
}↵
// building a strong aryan base to rule the world↵
int* aryans=(int*)malloc((max(LIS,LDS)+1)*sizeof(int));↵
for(int i=0;i<n;i++)is_aryan[i]=0;↵
if(LIS>LDS){↵
int curr_aryan=ss[LIS-1][1];↵
for(int i=0;i<LIS;i++){↵
aryans[LIS-i-1]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev1[curr_aryan];↵
}↵
aryans[LIS]=HITLER;↵
}↵
else{↵
int curr_aryan=gestapo[LDS-1][1];↵
for(int i=0;i<LDS;i++){↵
aryans[i]=germany[curr_aryan];↵
is_aryan[curr_aryan]=RACE_THEORY;↵
curr_aryan=prev2[curr_aryan];↵
}↵
aryans[LDS]=HITLER;↵
}↵
// gathering the jews↵
int* jews=(int*)malloc((n-max(LIS,LDS))*sizeof(int));↵
int jew_nose_size=n-max(LIS,LDS);↵
jew_index=0;↵
for(int i=0;i<n;i++){↵
if(!is_aryan[i])jews[jew_index++]=germany[i];↵
}↵
hitler_sort(jews,n-max(LDS,LIS));//get the jews in order↵
// merge west germany and east germany↵
int jew_counter=0/*need to get that up to 6e6*/,nazi_counter=0/*need to get that up to the whole world*/;↵
for(int i=0;i<n;i++){↵
if(jew_counter!=jew_nose_size&&jews[jew_counter]<aryans[nazi_counter])germany[i]=jews[jew_counter++];↵
else germany[i]=aryans[nazi_counter++];↵
}↵
free(aryans);↵
//we do not free(jews);↵
}↵
int main(){↵
int n;scanf("%d",&n);↵
int* v=(int*)malloc(n*sizeof(int));↵
for(int i=0;i<n;i++){↵
scanf("%d",v+i);↵
}↵
hitler_sort(v,n);↵
for(int i=0;i<n;i++){↵
printf("%d ",v[i]);↵
}↵
free(v);↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Story behind the algorithm (Nazi)">↵
the theory: kill the jews!↵
we propose the following sorting method:↵
we will call a monotone sequence an aryan sequence, and we will fix germany such that it will be aryan.↵
by the Erdős–Szekeres theorem we know that there is an aryan subsequence of length at least √n, will can find it using well known LIS finding algorithms.↵
after we found the aryan subsequence we will build two new arrays, one will be the aryan subsequence, and the other will be the jews.↵
next, we propose that germany will fix the damn jews and get them back in order, so we recursivly sort the jews.↵
now that we have the aryans and the sorted jews, we will reverse the aryans if they are decreasing and then we will merge the aryans and sorted jews to get a united germany.↵
the time until we finish the war is ↵
$T(n)=O(nlogn)+T(n-√n) \implies T(n)=O(n√nlogn)$↵
</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!↵
↵
