Implement Merge Sort Algorithm in JavaScript

Merge Sort is a highly efficient, comparison-based sorting algorithm known for its stability and predictable performance. Understanding and implementing Merge Sort is a fundamental step in mastering algorithmic concepts and developing robust sorting solutions in JavaScript.

Problem Description

Your task is to implement the Merge Sort algorithm in JavaScript. This algorithm recursively divides an unsorted array into smaller subarrays until each subarray contains only one element (which is considered sorted). Then, it repeatedly merges these sorted subarrays to produce new sorted subarrays until there is only one subarray remaining, which is the sorted version of the original array.

Key Requirements:

• Implement a function mergeSort(arr) that takes an array of numbers (arr) as input and returns a new array containing the elements of arr sorted in ascending order.
• The implementation should be a true Merge Sort, utilizing its divide-and-conquer strategy.
• The original input array should not be modified.

Expected Behavior:

The function should return a new sorted array.

Edge Cases:

• An empty array.
• An array with a single element.
• An array with duplicate elements.
• An array that is already sorted.
• An array sorted in reverse order.

Examples

Example 1:

Input: [3, 1, 4, 1, 5, 9, 2, 6]
Output: [1, 1, 2, 3, 4, 5, 6, 9]
Explanation: The array is recursively divided, and then sorted subarrays are merged until the entire array is sorted.

Example 2:

Input: [5, 2, 8, 1, 9]
Output: [1, 2, 5, 8, 9]
Explanation: Similar to Example 1, the algorithm breaks down the array and reconstructs it in sorted order.

Example 3:

Input: []
Output: []
Explanation: An empty input array should result in an empty output array.

Example 4:

Input: [7]
Output: [7]
Explanation: An array with a single element is already considered sorted.

Constraints

• The input array will contain only numbers.
• The size of the input array will be between 0 and 10,000 elements, inclusive.
• The numbers in the array will be within the range of standard JavaScript number types.
• The algorithm's time complexity should ideally be O(n log n).
• The algorithm's space complexity should ideally be O(n) due to the need for auxiliary space during merging.

Notes

• Merge Sort typically involves two main parts: the recursive splitting (divide) and the merging of sorted subarrays.
• You will likely need a helper function to perform the merging of two sorted arrays.
• Consider how you will handle the base case for the recursion (when a subarray has 0 or 1 element).
• Remember to create new arrays during the merge step to avoid modifying existing ones and to ensure correctness.