Array is sorted!
Merge Sort is a divide-and-conquer sorting algorithm that splits the input list into two halves, recursively sorts each half, and then merges the sorted halves back together. This process continues until the entire list is sorted.
Time Complexity:
Best Case: O(n log n) (due to the division of the list)
Average Case: O(n log n)
Worst Case: O(n log n)
Space Complexity:
O(n) (requires additional space for the temporary arrays used during merging)
Merge Sort is efficient for large datasets and guarantees O(n log n) time complexity regardless of the initial order of elements. However, its additional space requirement makes it less memory efficient than in-place algorithms.