What is the time complexity of Merge Sort and how does it work?

Time Complexity of Merge Sort and How It Works

Merge Sort is a sorting algorithm with a time complexity of O(n log n). It follows a divide and conquer approach to sorting elements.

The algorithm works by dividing the array into two halves, recursively sorting each half, and then merging the two sorted halves. Here is a high-level overview of how Merge Sort works:

1. Divide the array into two halves
2. Recursively sort each half
3. Merge the sorted halves together

By using this approach, Merge Sort achieves O(n log n) time complexity, making it one of the most efficient sorting algorithms available.