Implementing Merge Sort in JavaScript

Merge sort is a powerful and efficient sorting algorithm based on the divide-and-conquer paradigm. It recursively divides an array into smaller sub-arrays until each sub-array contains only one element (which is inherently sorted). Then, it repeatedly merges the sub-arrays to produce new sorted sub-arrays until there is only one sorted array remaining. This challenge asks you to implement merge sort in JavaScript.

Problem Description

You are tasked with creating a JavaScript function called mergeSort that takes an array of numbers as input and returns a new array containing the same numbers, sorted in ascending order using the merge sort algorithm. The function should not modify the original input array. The core of merge sort involves recursively dividing the array and then merging the sorted sub-arrays. Pay close attention to the merging process, ensuring that elements are compared and placed correctly in the final sorted array.

Key Requirements:

• Divide: Recursively split the input array into two halves until each sub-array contains only one element.
• Conquer: The single-element sub-arrays are considered sorted.
• Merge: Merge the sorted sub-arrays back together to produce larger sorted arrays. This involves comparing elements from the two sub-arrays and placing the smaller element into the merged array.
• Return: Return the fully sorted array.

Expected Behavior:

The mergeSort function should correctly sort arrays of any size, including empty arrays and arrays with duplicate elements.

Edge Cases to Consider:

• Empty array: Should return an empty array.
• Array with one element: Should return the array itself (already sorted).
• Array with duplicate elements: Should handle duplicates correctly, maintaining their relative order.
• Array with negative numbers: Should correctly sort arrays containing negative numbers.

Examples

Example 1:

Input: [5, 2, 8, 1, 9, 4, 7, 3, 6]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: The input array is recursively divided and merged to produce the sorted array.

Example 2:

Input: [3, 1, 4, 1, 5, 9, 2, 6]
Output: [1, 1, 2, 3, 4, 5, 6, 9]
Explanation: The algorithm correctly handles duplicate values and sorts them in ascending order.

Example 3:

Input: []
Output: []
Explanation: An empty array remains empty after sorting.

Example 4:

Input: [-5, 2, -8, 1, 0]
Output: [-8, -5, 0, 1, 2]
Explanation: The algorithm correctly sorts an array containing negative numbers.

Constraints

• The input array will contain only numbers (integers or floats).
• The input array can be of any length, including 0.
• The function must not modify the original input array.
• The time complexity of the algorithm should be O(n log n).
• The space complexity should be O(n) due to the auxiliary space used during merging.

Notes

• The merge function (which merges two sorted arrays) is a crucial part of the merge sort algorithm. Consider how to efficiently compare elements from the two arrays and build the merged array.
• Recursion is key to implementing the divide-and-conquer strategy. Make sure your base case (when to stop the recursion) is correctly defined.
• Think about how to create a new array for the merged result without modifying the original sub-arrays. This is important to maintain the integrity of the original data.
• While not strictly required, consider adding comments to your code to explain the logic and steps involved in the algorithm. This will improve readability and understanding.