Hello! Codeforces , This is an new algorithm of sorting by combining two idea's(Merge sort and square root decomposition).
Idea : Lets say n is the size of the array. Lets define some integer m, and divide our array chunks of size m. We know the number of chunks will be n/m . So lets sort all these small chunks and than using the idea of merge sort merge all of the sorted n/m chunks.
Now here is a point while merging our solutions we don't have to merge them all at once. Why is that? A simple analysis is that for every position I am spending O(n/m) time so total O(n^2 / m). But can we some how do this better to have low comparisons. And the Answer is YES.
But How? Just take the first two of the chunks and merge them. Then take the next two and so on ... . Then with these merged chunks repeat the operation until we have only one chunk which of size n. Now how does this improves. Now every time my number of chunks are dividing by 2 and the size of each one of the chunks is getting bigger by a factor of 2.
Now lets see how many time the size of the chunk that contains the number i increase. So as our growth is exponential this gives us the time of (lg (n/m)). So the total for n elements it's time of O(n lg(n/m)). Now this is Huge better.
Now we wanted to see what is the total runtime.
The Recursive formula for this is
Now what is the value of m can we give to this. Lets use the idea of square root decomposition ans say m = √n.
What will be the runtime : O(n lg n)
How this is solve see this.
Hope you like this algorithm.
We can also choose m = n/2 , but than this is merge sort(But world wanted something different).
Also the credit of computing the runtime goes to secretno_botaem.
