Implementing Quicksort in JavaScript

Quicksort is a highly efficient, widely used sorting algorithm that operates on the principle of "divide and conquer." Your task is to implement the Quicksort algorithm in JavaScript. This challenge will test your understanding of recursion, array manipulation, and algorithmic efficiency.

Problem Description

You are required to implement the Quicksort algorithm to sort an array of numbers in ascending order. The algorithm should:

1. Select a pivot: Choose an element from the array to serve as the pivot. The choice of pivot can influence performance, but for this challenge, you can use the first element of the subarray as the pivot.
2. Partition: Rearrange the array such that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it. The pivot element is now in its final sorted position.
3. Recursively sort: Recursively apply the Quicksort algorithm to the subarrays before and after the pivot.
4. Base Case: The recursion should stop when the subarray has zero or one element, as these are already sorted.

The function should take an array of numbers as input and return a new array containing the sorted elements. The original array should not be modified.

Examples

Example 1:

Input: [5, 2, 8, 1, 9, 4, 7, 6, 3]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: The array is sorted in ascending order using the Quicksort algorithm.

Example 2:

Input: [10, 7, 8, 9, 1, 5]
Output: [1, 5, 7, 8, 9, 10]
Explanation: Another example demonstrating the sorting of an unsorted array.

Example 3: (Edge Case)

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

Example 4: (Edge Case)

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

Constraints

• The input array will contain only numbers (integers or floats).
• The input array can be empty.
• The input array can contain duplicate numbers.
• The algorithm should have an average time complexity of O(n log n). While worst-case O(n^2) is possible, your implementation should generally avoid it.
• The function should not modify the original input array. It must return a new sorted array.

Notes

• Consider using a helper function to handle the recursive calls. This can improve code readability.
• The choice of pivot significantly impacts performance. While using the first element is acceptable for this challenge, be aware that more sophisticated pivot selection strategies (e.g., random pivot) can help avoid worst-case scenarios.
• Pay close attention to the base case of the recursion to prevent infinite loops.
• Remember to create a new array to store the sorted result, leaving the original array unchanged.