mergesort dividing the sequence not into half

Question

usually, mergesort is performed by dividing the sequence into half and recursively sorting it. however is it also possible to 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 this work? And if it does, What will the bigO notation be?

Accepted Answer

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

mergesort dividing the sequence not into half

Solution

Problem