Merge Sort Complexity

This lecture explains the complexity of merge sort, highlighting that it operates with a time complexity of O(n log n) due to log n decompositions and n comparisons at each level. The complexity remains consistent across best, worst, and average cases, as the process does not depend on input type. The lecture also covers the merge process, emphasizing the need for comparisons and the use of extra space, resulting in a space complexity of O(n). The session concludes with a reminder to understand divide and conquer and recursion for implementation in the next lecture.

Summarize the overall complexity of merge sort.

Describe the space complexity of merge sort.

What does 'divide and conquer' mean in the context of merge sort?