Merge Sort

Merge Sort is a divide and conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves into one sorted array. Merge Sort is an efficient, comparison-based, and stable sorting algorithm.

How it Works:

Divide: The array is recursively split into two halves until each sub-array contains a single element (which is trivially sorted).
Conquer: Each pair of sub-arrays is merged back together, ensuring the elements are in sorted order.
Combine: The merging process continues until all sub-arrays have been merged into a single sorted array.

Time Complexity:O(nlogn)
Space Complexity:O(n)

Merge Sort guarantees O(nlogn) performance in all cases, while Quick Sort has a worst-case performance of O(n²), though Quick Sort is often faster in practice because of better cache performance and smaller constant factors.