Time and Space Complexity

Time Complexity:

• Best, Average, and Worst Case: O(n log n)
  • The array is split in half about log n times, and each level does O(n) work to merge. The running time does not depend on the input order.

Space Complexity:

• O(n)
  • Unlike in-place sorts, Merge Sort builds new arrays while merging, so it needs extra memory proportional to the input size.

Summary:

• Merge Sort is fast and predictable: O(n log n) in every case.
• It is stable, so equal elements keep their order.
• The trade-off is the extra O(n) memory it uses for merging.