Merge Sort: Space

• Merging cannot be done in place

• In the simplest case, a separate list of size n is required for merging

• It is possible to reduce the size of the extra space, but it will still be ?(n)

Previous slide

Next slide

Back to first slide

View graphic version