Question

Merge Sort

03 Nov 2017
Answer :
Word Count : 704

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 O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case.[citation needed]

Recursive implementations of merge sort make 2n − 1 method calls in the worst case, compared to quicksort's n, thus merge sort has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive implementations of merge sort, avoiding

____ ________ ____ _____ _______ _____ _________ _____ _______ ______ _________.
___ ___ ________ ______ ________ _________ __________ _____.
______ ___ _____ ___ ___ ______ ____ ___ ______.
_____ _____ ___ ___ _________ ________ _______ ___ ____ ________.
_________ ________ ____ _________ ______ ___ _________ ___ __________.
________ ___ ________ ____ _________.
__________ ___ _______ __________ ________ __________ ______ ____ __________ ________ ______ _______.
______ ________ _________ ________ __________ __________ _______ __________ ___ _________ ___.
________ ___ ______ _________ ____.
________ _________ ________ _____ _____ __________ _______ _________.
___ ____ _______ ____ _____ _____ _________ ________ _________ ________.
______ ____ _________ _________ _______ ________ ____ _____ ___ _______.
_________ _____ ___ _______ __________ ________ ________.
________ _________ ________ _______ ______.
__________ _________ ________ ________ _________ ___ _______.
_______ ______ _______ ___ ____ ___ _____ ______ ________ _______.
__________ _________ ______ _________ ______ ______ ________ _____.
_____ ___ ____ ____ ____.
_____ _______ ________ ______ ____ _______ ________ ______ _______ __________.
_____ _____ ___ _______ ___ _____.
_____ _________ __________ ______ ________ _____ _____ ______.
__________ _________ ________ _____ __________ __________.
_________ _____ ___ ____ ______.
_________ ___ _____ ________ ____.
____ _____ _______ _____ ________ ___ ___ ________.
___ _______ _______ _________ ______ __________ _______ _______.
______ __________ ____ _____ ________ ______ ____.
__________ _____ ___ __________ ___ ____.
__________ __________ _______ ____ ______ ____ ___ _________ ____.
_______ ________ ____ ___ _____ _________ ____ __________.
___ ________ _________ _______ ________ _______ ___.
________ ____ ___ __________ ______ _______ _________ _________.
___ __________ _____ ________ _____ _______ ___.
__________ __________ _________ ___ ________ __________ _______.
______ __________ ________ ___ ________ _________ ________ ____.
_________ ___ ____ __________ ______ ______.
__________ ______ ____ ______ ____ __________ ______.
______ ___ ________ ___ _______ _____ _________ ______ _______ ___.
_____ __________ ______ ___ __________ ____ ________ _________.
___ _________ ____ _________ ______ ______ ________ _______ _______ ______ ____.
____ _______ ______ ___ ___ _________.
_________ ______ _________ ______ ______ ___.
___ ___ ______ _______ _______ ___.
____ _____ ___ _______ _______ ____ ______ ______ ______ ______ _________ ____.
__________ ______ ________ ______ _______ ___ ______ __________ _________.
_______ ___ ______ __________ __________ ________ _______ ____ _______.
___ ____ __________ __________ ______ ___ _____ __________ _________ _______.
____ ___ _______ __________ ______ _________ _____ ___ _________ ________ _______ ______.
__________ ________ ______ __________ _______ _________ ______ ____ ___ __________ _________ ___.
________ ________ ______ ________ _______ ___ ______ ________ ________ _______ _________.
____ __________ ___ ___ ________ ________ _______ __________ ______.
_________ ___ _______ __________ ____ _________ ___ ______.
___ _______ _________ ______ __________ _______ ________.
_____ ______ _____ ___.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU MCS 31 2011 - Merge Sort | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→