Seth.

Merge Sort - Technical Overview

1. Algorithm Description: Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts both halves, and then merges the sorted halves back together.

2. Steps of Merge Sort:

• Divide the unsorted array into n subarrays, each containing one element (a sorted array of one element).
• Repeatedly merge subarrays to produce new sorted subarrays until there is only one subarray remaining (the sorted array).

3. Time Complexity: O(n log n) in the worst, average, and best cases.

4. Space Complexity: O(n), as it requires additional space for temporary arrays during merging.

5. Stability: Merge Sort is a stable algorithm.

6. Suitability: Suitable for large datasets and linked lists, but requires more space compared to in-place sorting algorithms.