Menu
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?
481
It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
What Is a Merge Sort Algorithm? Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list.
The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn) Best Case Time Complexity: O(n*log n) Worst Case Time Complexity: O(n*log n) Average Time Complexity: O(n*log n) The time complexity of ...
In theory, it's because the merge procedure needs to take two sorted lists. A 4-elements list isn't sorted, while a one-element list is. In practice, we don't split lists to one-element. Because merge sort isn't the most efficient sorting algorithm for small lists, insertion sort is.
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.
107
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
