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.
C++ Code (Nazi version)#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;
}
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; }
Python Code (clean)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()
C Code (Nazi version & optimized for time)#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;
}
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)$$$
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}^{\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))$$$.
Thank you for reading this far, we hope you enjoyed this blog and would love to hear comments and ideas.
danke und auf Wiedersehen!
