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?

Answer 1

Yes, it will certainly work, but the strength of mergesort is the recursive divide-and-conquer approach. If you split the list into halves each time, then you will 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 big O expression will still be O(log n), because you split the list into several parts at each level, but it may be slower than splitting the list in half, because the algorithm will not be working at its most optimal, which is splitting the list, sorting each part, and merging the sorted sublists. As food for thought, imagine what would happen if mergesort picked only the first item as the left sublist, and every other item as the right sublist. Then the big O expression would O(n^2), which is as bad as other, worse, algorithms. Of course, if you want to try out your thoughts, just do so, and time it! Then you would know for sure what is faster.