Quick sort implementation | beats 98%
IntuitionWe need to sort an array based on a custom function fn. The function transforms each element, and we compare the transformed values to determine the or
# Intuition
We need to sort an array based on a custom function `fn`. The function transforms each element, and we compare the transformed values to determine the order. QuickSort is a good choice because it efficiently sorts in-place with an average time complexity of `O(n log n)`.

# Approach
1. Copy the input array to avoid modifying the original.
2. Implement the QuickSort algorithm with a custom comparison using `fn()`.
3. Partition the array based on the transformed values.
4. Recursively sort the left and right subarrays.

# Complexity
![image.png](https://assets.leetcode.com/users/images/a409e362-c2d1-45de-9f62-cb81f7d3b26d_1741079221.9126496.png)

- Time complexity:  
  - **Average case**: $$O(n \log n)$$  
  - **Worst case**: $$O(n^2)$$ (if the pivot selection is poor)
- Space complexity:  
  - **Worst case**: $$O(n)$$ (due to recursive function calls)

# Code
```Javascript []
var sortBy = function (arr, fn) {
    let res = [...arr]; // Create a copy of the array
    quickSort(res, 0, res.length - 1);
    return res;

    // QuickSort with a custom comparison function
    function partition(myArr, low, high) {
        let pivot = myArr[high];
        let i = low - 1;

        for (let j = low; j < high; j++) {
            if (fn(myArr[j]) < fn(pivot)) {
                i++;
                [myArr[i], myArr[j]] = [myArr[j], myArr[i]]; // Swap elements
            }
        }
        [myArr[i + 1], myArr[high]] = [myArr[high], myArr[i + 1]]; // Place pivot correctly
        return i + 1;
    }

    function quickSort(myArr, low, high) {
        if (low >= high) return;
        let pi = partition(myArr, low, high);
        quickSort(myArr, low, pi - 1);
        quickSort(myArr, pi + 1, high);
    }
};
```
['Sorting', 'Merge Sort', 'JavaScript']