Merge Sort

Time Complexity:

• Best: O(n log n)
• Average: O(n log n)
• Worst: O(n log n)

Space Complexity: O(n)

Stable: Yes

Merge Sort uses a divide-and-conquer strategy: it recursively splits the array into smaller subarrays until each contains a single element.

Then it merges these sorted subarrays back together, comparing elements and placing them in the correct order, until the entire array is sorted.