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.

#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;
}

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()

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)$$$

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))$$$.

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!