Write a function to sort an input array using the merge sort algorithm. Merge sort is a divide and conquer algorithm that divides the input array into two halves, sorts each half using recursion, and then merges the two sorted halves to output one sorted array in ascending order. Your function should take in an array as input and return a sorted array.

## Walkthrough

The merge sort algorithm is a recursive algorithm that works by dividing the input array into two halves, sorting each half, and then merging the two sorted halves. We'll start by writing a function to merge two sorted arrays, as we'll need this helper function to implement the merge sort algorithm.

```
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
```

The `merge`

function takes in two arrays, `left`

and `right`

, and returns a new sorted array that merges the two input arrays. We start by initializing an empty array `result`

, and two indices, `leftIndex`

and `rightIndex`

, to keep track of the current positions in the left and right arrays. We loop through the left and right arrays until we've gone through all the elements in either array. In each iteration, we compare the current element in the left array with the current element in the right array. If the element in the left array is smaller, we add it to the result array and increment `leftIndex`

. Otherwise, we add the element in the right array to the result array and increment `rightIndex`

. Finally, we concatenate any remaining elements in either the left or right array to the result array and return the sorted array.Next, we can write the `mergeSort`

function to implement the merge sort algorithm. The `mergeSort`

function takes in an array and recursively sorts it using the `merge`

function.```
function mergeSort(array) {
const length = array.length;
if (length < 2) {
return array;
}
const middle = Math.floor(length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
```

The `mergeSort`

function starts by checking if the length of the input array is less than 2. If so, the array is already sorted and we can return it. Otherwise, we find the middle index of the array using `Math.floor(length / 2)`

, and use the `slice`

method to create new left and right arrays. We then recursively call `mergeSort`

on the left and right arrays, which will continue to divide the arrays into smaller halves until they are sorted. Finally, we return the merged and sorted left and right arrays using the `merge`

function.**Big O Complexity Analysis:**

The merge sort algorithm has a time complexity of O(n log n), where n is the number of elements in the input array. The algorithm works by recursively dividing the input array in half, sorting each half, and then merging the sorted halves.

In each level of recursion, the array is divided into two halves, and the `merge`

function is called once to merge the two halves. The `merge`

function takes O(n) time to merge two arrays of length n/2, and since there are log n levels of recursion (because we're dividing the array in half each time), the total time complexity of the `merge`

function is O(n log n).The `mergeSort`

function also takes O(n log n) time to sort the input array, since it recursively divides the array in half and then calls the `merge`

function at each level of recursion.The space complexity of the merge sort algorithm is O(n), since the algorithm creates a new temporary array to merge the left and right halves at each level of recursion. This temporary array has a length of n, which is the maximum size of the input array. Therefore, the space complexity of the merge sort algorithm is proportional to the size of the input array.