Merge Sort: Analysis

• Sorting requires no comparisons

• Merging requires n-1 comparisons in the worst case, where n is the total size of both lists (n key movements are required in all cases)

• Recurrence relation:

Previous slide

Next slide

Back to first slide

View graphic version