Bottom-Up Mergesort Analysis
lMerging
two sequences of length n/2 each can be done in O(n) if linked lists are
used.
lIn merge sort of n elements, we merge:
n/2 pairs of sequences of length 1
n/4 pairs of sequences of length 2
n/8 pairs of sequences of length 4
É
1 pair of sequences of length n/2
lIn merge sort of n elements, we merge:
n/2 pairs of sequences of length 1
n/4 pairs of sequences of length 2
n/8 pairs of sequences of length 4
É
1 pair of sequences of length n/2