# Merge Sort

ARRAY

SORTING

### 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

- Divide the unsorted array into two approximately equal parts.
- Recursively sort each sub-array.
- 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.

Loading...