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 1n/4
pairs of sequences of length 2n/8
pairs of sequences of length 4É1
pair of sequences of length n/2