Merge Sort
In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem.
In the worst case, merge sort does an amount of comparisons equal to or slightly smaller than (n ⌈lg n⌉ - 2⌈lg n⌉ + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).[2]
For large n and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches α·n fewer than the worst case where
In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is
_________ _______ ______ ___ _______.
_____ _____ _________ _____ _________ _____ _______ ________ ___ _____ ______.
__________ ___ _____ _________ _____ ________ ____ __________ ____.
____ ______ ________ ______ ________.
___ _________ ________ __________ ______ ____ ____ _________.
______ __________ __________ ____ _______ _______ ________.
_________ _________ ___ __________ ____ __________ _____ _____ ______.
_________ ________ ______ _________ ____ __________ ________ _______ _________ ___ ________ _________.
_________ ___ __________ _____ _______ _____ __________ ____ ____ ___.
________ _______ ____ ___ _________ ____ ________ _________ ___ __________.
___ _____ _______ _________ _______ ___ _____.
__________ _____ ____ ______ _______ ___ ___ _________ ______ ___ _______ __________.
___ ____ __________ _______ _____ ________ ____ ______ _______ _________ ______.
____ __________ _________ ______ ____.
_______ _____ __________ ______ _________ _______ ________.
________ __________ ___ _______ ___ ___ ______ __________ __________.
____ ________ __________ ___ _____.
____ ___ __________ ___ __________ ________ _______.
_____ _________ _____ ______ ___ _________ ____ _____ _____ ____.
___ _______ ______ _______ _____ _____ ____ _______ ___ ________.
______ _________ ____ ____ ___ _________ ___ ________ _________ _________.
__________ _____ ___ _____ __________ ________ _____.
________ _______ ___ ___ ________ ______ ________.
_____ _____ ____ _________ ___ ______ ______.
_____ ____ __________ _________ _________ ____ _________ ______.
________ ______ _____ _____ _________ _________ ______ ____ ________ ____ ____.
________ _____ ______ ____ __________ ______ _____ ____.
____ ____ ________ ______ ____ _____ _____ _______ _______ ___ __________ _________.
___ ____ _________ _______ ________.
________ ____ ______ _______ _______ _____ _________ _______ __________ ____ _________.
___ ________ ___ ________ _______ ________ _____ ________ ____ _______ _____.
______ ____ ________ ________ _____ _____ ___.
________ _______ __________ ____ ___ ___ _________ ________ _________ _____ ____.
___ _________ ____ _________ ____.
______ ______ ______ ____ ___ __________ __________ _______ _________ _____ ____.
__________ ________ ________ ____ _______.
_______ ______ __________ ___ ___ __________ __________ ___ __________ __________ ________.
____ ______ ________ _________ __________ ______ __________ _________ _____ _____ _______ _______.
_________ _________ ___ _______ _______ ____ _______ ________ __________ _________ ____ _______.
________ _____ ________ ____ _____ ________ ________ __________.
__________ ____ __________ ___ __________ __________ _________.
_____ __________ _______ _______ __________ _________ _______ ___.
_________ _______ ___ _______ _____ ________ ___ _________ _________ __________ ______.
_______ ___ ______ __________ _______.
_______ ___ _______ _________ __________ _____ ___.
_______ ________ __________ _____ __________ ________ _____ _________.
______ ___ __________ _______ ___ _______ ______.
_________ ______ ___ _______ ___ ___ ______ _______ _______ _____.
_________ _______ ____ _________ ______ ______ __________ _________ ______ _______ ___.
___ ______ _______ ________ _____ _______ ___.
_______ ____ ___ ______ ___ ______ ____ ___ ________ ____ _______ ___.
___ __________ _______ _____ ______ ______ ____ ____.
________ _________ ____ ________ __________.
___ __________ ___ ____ _____ ________ _________ ______ ____ ______ ______ ______.
_________ __________ __________ ______ _________ _________ ___ __________.
_____ ________ ___ ____ ____ ________ _________ ____ _________ _______ ________.
__________ _________ _________ ____ ____.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required