mergesort dividing the sequence not into half

mergesort
안진원 picture 안진원 · Apr 27, 2013 · Viewed 8.3k times · Source

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?

Answer

Fred Foo picture Fred Foo · Apr 27, 2013

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

Related questions

How to merge two sorted arrays into a sorted array?

This was asked of me in an interview and this is the solution I provided: public static int[] merge(int[] a, int[] b) { int[] answer = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length &…

Read More
Why is quicksort better than mergesort?

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

Read More
How to sort in-place using the merge sort algorithm?

I know the question is not too specific. All I want is someone to tell me how to convert a normal merge sort into an in-place merge sort (or a merge sort with constant extra space overhead). All I can …

Read More