Mergesort not dividing the sequence by half

Question

usually, mergesort is done by dividing the sequence by half and recursively sorting. however, can you also perform mergesort by dividing the sequence by a third?

mergesort(array, start, last) { tri_mid = (start+last)/3; mergesort(array, start, tri_mid); mergesort(array, tri_mid+1, last); merge(array, start, last); } 

will it work? And if that happens, what will bigO stand for?

Answer 1

This should work fine if you turn on the third recursive call and write the merge procedure correctly. By the master theorem, complexity is still O (n log n).

Answer 2

Yes, it will certainly work, but the power of mergesort is a divide-and-conquer recursive approach. If you split the list in half each time, then you get O (log2 (n)), but this is equivalent to O (log n) because of how computational complexity works. If you split the list into two parts that are not equal, then your large O expression will still be O (log n), because you split the list into several parts at each level, but it can be slower than halving the list. because the algorithm will not work on the most optimal one, which splits the list, sorts each part and combines the sorted sublists. Imagine what happens if mergesort selects only the first item as the left sublist and each other item as the right sublist. Then the large expression O will be O (n ^ 2), which is as bad as the other, worse, algorithms. Of course, if you want to try your thoughts, just do it and it's time! Then you know exactly which is faster.

Answer 3

Well, I figured it out →

Let's say we want to combine not 2 arrays, but r no arrays.

And let the total number of elements n

When merging, we will access the data elements from each array, and then compare with others to find out the minimum (for the ascending order) that will be added to the combined array.

The work done in comparison and finding the minimum value will be O (r). And since the total number of elements added to the combined array is n , So:

  Complexity to merge r arrays with total elements n will be O(nr) 

Applying the above result to Mergesort, where the array is divided into r smaller arrays each time

Since the array is each time divided into r smaller arrays, the process of division and merging will continue for log _r n times.

So the complexity of such a Mergesort would be O (nrlog _r n)

Now let's try to find out that for some given n, what value of r will make the least complexity. For this, the function F (r) = nrlog _r n must be differentiated with respect to r and in the usual way found what is the value r = e (2.71) , which is not an integer. Also, the function begins to increase after this minimum point. Therefore, the integral value of r for which the complexity function is less than either 2 or 3 But (2nlog ₂ n - 3nlog ₃ n)> 0

So, the required value of r is 3

Therefore, Mergesort, dividing the array into 3 smaller ones, and then merging, should have the best mergesort .

Answer 4

If you divide the array into three parts, the recursive equation for time complexity will be: T (n) = 3T (n / 3) + O (n). Using the main theorem, the time complexity will still be O (nlogn). Even if you divide the array into as many equal parts, the asymptotic complexity will remain the same. The reason for this is because you have to do two things in each recursion, i.e. share and unite. Merging will always take O (n) time. Therefore, if you are thinking about minimizing your time complexity, try to think of an algorithm that can combine two sorted arrays in less than O (n) time.

Answer 5

Here you have an example of such a merge :-)

 void TRIPLE_MERGESORT(vector<double> &A, int k, int l) { if(k<l) { int one_third = (lk)/3; int two_third = 2*(lk)/3; // k < k+one_third < k+two_third < l TRIPLE_MERGESORT(A,k,k+one_third); TRIPLE_MERGESORT(A,k+one_third+1,k+two_third); TRIPLE_MERGESORT(A,k+two_third+1,l); MERGE(A,k,k+one_third,k+two_third); MERGE(A,k,k+two_third,l); } } 

Where MERGE combines arrays (vectors) that can be implemented, for example, as:

 void MERGE(vector<double> &A, int p, int q, int r) { int i = p; int j = q+1; int lenght = r - p + 1; int k=0; vector<double> merged; merged.assign (lenght,0); while((i<=q)&&(j<=r)) { if(A[i] <= A[j]) { merged[k]=A[i]; ++i; } else { merged[k]=A[j]; ++j; } k++; } if(j<=r) { while(j<=r) { merged[k]=A[j]; ++j; ++k; } } if(i<=q) { while(i<=q) { merged[k]=A[i]; ++i; ++k; } } for (i=0;i<lenght;++i) A[p+i]=merged[i]; } 

A good day:)

// EDIT: //

It is impossible to say for sure (but probably someone else will say it better and why it is), but splitting into 3 parts is more complicated (and requires more work) than a regular merge, so it will take more time. I think it will be O (n ^ 2), but certainly worse than a regular merge :)