Time Complexity
Merge-sort has a guaranteed worst-case time complexity of Θ(n log₂ n).
It is quite nice to understand why graphically.
First of all, we concentrate on the merging operation, which takes time Θ(n1 + n2) = Θ(n), since each of the n1 elements in t1 is copied exactly once into a and each of the n2 elements in t2 is also copied exactly once into a.
Let us now imagine the initial array and its two sub-ranges:
* * * * * * * * * * * * * * * *
* * * * * * * *|* * * * * * * *The running time of a recursive call is dominated by:
- sorting the two subranges, and
- the merging operation,
since the other operations in the call take constant time.
The running time of a call to sort_range is therefore the sum of the running time for the recursive calls and the running time for the merging operation.
As discussed, the merging takes time Θ(n) = Θ(n1 + n2), so we count n time units for merging. We place n tokens onto the elements of the initial array, one token for each time unit taken by the merging operation.
. . . . . . . . . . . . . . . .
* * * * * * * * * * * * * * * *
* * * * * * * *|* * * * * * * *It remains to add tokens for the recursive calls. To do this, we concentrate on each of the two sub-ranges in turn.
Each of the two sub-ranges is also split into two sub-sub-ranges.
. . . . . . . . . . . . . . . .
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * *|* * * *
. . . . . . . . . . . . . . . .
* * * * * * * * * * * * * * * *
* * * * * * * *|* * * * * * * *
* * * *|* * * *|* * * *|* * * *As the sub-subranges are merged into the initial sub-range, we add the tokens necessary for this merging step.
After accounting for the first recursive call
. . . . . . . . . . . . . . . . (token accounting for
* * * * * * * * * * * * * * * * merging the first sub-range)
. . . . . . . .
* * * * * * * *|* * * * * * * *
* * * *|* * * *|* * * *|* * * *
After accounting for the second recursive call as well
. . . . . . . . . . . . . . . . (token accounting for
* * * * * * * * * * * * * * * * merging the second sub-range)
. . . . . . . . . . . . . . . .
* * * * * * * *|* * * * * * * *
* * * *|* * * *|* * * *|* * * *This process gets repeated until we reach sub-…-sub-ranges of 1 or 0 elements. These ranges, with 0 or 1 elements, also get a token, since the recursive call, even if it does no real work, takes constant time (Θ(1)).
. . . . . . . . . . . . . . . .
* * * * * * * * * * * * * * * *
. . . . . . . . . . . . . . . .
* * * * * * * *|* * * * * * * *
. . . . . . . . . . . . . . . .
* * * *|* * * *|* * * *|* * * *
. . . . . . . . . . . . . . . .
* *|* *|* *|* *|* *|* *|* *|* *
. . . . . . . . . . . . . . . .
*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|*It remains to count the number of tokens. There are n tokens horrizontally, so the challenge is to count the number of rows.
. . . . . . . . . . . . . . . . \
* * * * * * * * * * * * * * * * \
. . . . . . . . . . . . . . . . |
* * * * * * * *|* * * * * * * * |
. . . . . . . . . . . . . . . . | log₂(n) rows
* * * *|* * * *|* * * *|* * * * |
. . . . . . . . . . . . . . . . |
* *|* *|* *|* *|* *|* *|* *|* * |
. . . . . . . . . . . . . . . . /
*|*|*|*|*|*|*|*|*|*|*|*|*|*|*|* /Each row has sub-ranges approximately half the size of the sub-ranges in the row above. The number of times we split an entity into halves until we reach an entity of size one is exactly the definition of the function log₂. Therefore, there are about log₂(n) rows.
We now count the number of tokens: there are n tokens horizontally times about log₂(n) tokens vertically, and therefore there are n log₂(n) tokens overall. Each token represents a unit of time. Therefore the algorithm terminates in n log₂(n) units of time, which means it has a time complexity of Θ(n log₂(n)).
Enjoyed our tutorial on merge-sort?
Cannot wait to understand more interesting algorithms and data structures?
Subscribe to the TrulyUnderstandingAlgorithms Youtube channel to stay up to date with our videos.
Also consider liking our video and leaving a comment with topics that you would like to us cover in the future.
Page 1 – Introduction
Page 2 – How it Works
Page 3 – Implementation
Page 4 – Time Complexity