Skip to main content
Lesson 25 - Merge and Mergesort
Lesson MenuPreviousNext
  
Order of Recursive Mergesort page 6 of 9

  1. Suppose we have a list of 8 numbers. If we trace the migration of one value, it will be a member of the following sizes of lists: eight, four, two. The number of calls of mergesort needed to sort one value into its final resting spot is log2N. If N = 8, then it will take three calls of the algorithm for one value to find its final resting spot.

  2. We must apply log2N steps to N elements in the list. The order of recursive Mergesort is O(N * log2N) or O(N * log N).

  3. What about the cost of merging the fragments of the list? The merge algorithm is a linear one, so when combined with the Mergesort routine we have a O(N * log N) + O(N), which remains in the category of an O(N * log N) algorithm.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.