Understanding Merge Sort

Merge Sort is a popular sorting algorithm that uses the Divide and Conquer paradigm. It is highly efficient and offers a stable sort with guaranteed time complexity.

How it works

1. Divide: Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
2. Conquer: Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This final merged sublist is the fully sorted array.
3. Merge: The core logic is the merge operation, which takes two sorted arrays and merges them into a single sorted array by comparing items sequentially from both.

Mathematical Complexities

• Best, Average, and Worst Case Complexity O(N log N): Re-dividing takes O(log N) steps, and merging at each level takes O(N) comparisons.
• Space Complexity O(N): Requires auxiliary space to store temporary merged partitions.

💡 Note: Merge Sort is extremely consistent and stable, meaning it preserves the original relative order of equal elements. However, its O(N) auxiliary space requirement is its main drawback compared to in-place sorts like Quick Sort or Heap Sort.