Merge Sort

Problem

Implement the merge sort algorithm to sort an array of integers in ascending order. The function mergeSort should take an array of integers as input and return a new array containing the sorted integers.

Algorithm

1. Divide the unsorted array into two approximately equal parts.
2. Recursively sort each sub-array.
3. Merge the two sorted sub-arrays into a single sorted array.

Examples:

mergeSort([9,4,7,3,5,8,1,6,2])
// returns [1,2,3,4,5,6,7,8,9]

Complexity

• Time Complexity: O(n log n) for all cases (best, average, and worst).
• Space Complexity: O(n), due to the additional space needed for merging.