Implement Quicksort in JavaScript

Quicksort is a highly efficient sorting algorithm known for its average-case performance. It's a divide-and-conquer algorithm that partitions an array into smaller sub-arrays and recursively sorts them. Mastering quicksort is a key step in understanding fundamental sorting techniques and recursive programming.

Problem Description

Your task is to implement the Quicksort algorithm in JavaScript. The function should take an array of numbers as input and return a new array containing the same numbers sorted in ascending order. You are free to choose your pivot selection strategy.

Key Requirements:

• Implement the Quicksort algorithm.
• The function should accept an array of numbers.
• The function should return a new sorted array; do not modify the original array in place.
• The sorting should be in ascending order.

Expected Behavior:

Given an array of numbers, the function should return an array with the elements arranged from smallest to largest.

Edge Cases to Consider:

• Empty arrays.
• Arrays with a single element.
• Arrays with duplicate elements.
• Arrays that are already sorted.
• Arrays that are sorted in reverse order.

Examples

Example 1:

Input: [3, 6, 8, 10, 1, 2, 1]
Output: [1, 1, 2, 3, 6, 8, 10]
Explanation: The input array is sorted into ascending order.

Example 2:

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

Example 3:

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

Example 4:

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

Constraints

• The input array will contain only numbers.
• The size of the input array can range from 0 to 1000 elements.
• The values of the numbers in the array will be between -1000 and 1000.
• The implementation should aim for reasonable performance, though strict time complexity analysis is not the primary focus for this challenge.

Notes

• Consider how to handle the partitioning step effectively.
• Recursion is a natural fit for Quicksort, but an iterative approach is also possible.
• Remember that Quicksort is typically an in-place algorithm, but for this challenge, you are required to return a new array to avoid modifying the original input. This might involve creating copies of sub-arrays during recursion.
• Think about different pivot selection strategies (e.g., first element, last element, median-of-three) and their potential impact on performance. For this challenge, any valid pivot selection is acceptable.