Runtime 143 ms Beats 6.31% & Memory 70.26 MB Beats 5.34%
IntuitionThe sortBy function sorts an array of elements based on the return value of a user-provided function fn. I decided to use the Quick Sort algorithm to r
# Intuition
The sortBy function sorts an array of elements based on the return value of a user-provided function fn. I decided to use the Quick Sort algorithm to recursively partition the array into smaller sub-arrays.

# Approach
Base Case:
If the input array has 0 or 1 element, it is already sorted, so return it.

Pivot Selection:
The function selects the last element of the array as the pivot.

Partitioning:
The function iterates through all elements except the pivot.
It compares the result of applying fn to each element with fn(pivot).
Elements for which fn(arr[i]) is less than fn(pivot) are added to the left sub-array.
Elements for which fn(arr[i]) is greater than or equal to fn(pivot) are added to the right sub-array.

Recursive Sorting:
The function recursively applies the same process to the left and right sub-arrays, and then combines the sorted left sub-array, the pivot, and the sorted right sub-array to return the fully sorted array.



# Complexity
- Time complexity:
  - Best Case:
   If the pivot divides the array into two equal halves at each step, the time complexity is O(n log n).
   This happens when the array is evenly partitioned.

  - Worst Case:
If the array is already sorted or reverse sorted, the pivot produces highly unbalanced partitions, resulting in a time complexity of O(n²).

  - Average Case:
On average, the time complexity is O(n log n).

- Space complexity:
  - Auxiliary Space:
   The space complexity of the sortBy function is O(n) due to the space required for:
The recursive call stack (up to O(log n) calls in the best case).
Temporary storage for the left and right sub-arrays (which can sum up to O(n) across recursive calls).
  - Overall Space Complexity:
O(n).

# Code
```javascript []
/**
 * @param {Array} arr
 * @param {Function} fn
 * @return {Array}
 */
var sortBy = function (arr, fn) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Choose a pivot element (here, the last element)
  const pivot = arr[arr.length - 1];

  // Arrays to hold the elements less than and greater than the pivot
  const left = [];
  const right = [];

  // Partition the array into left and right sub-arrays
  for (let i = 0; i < arr.length - 1; i++) {
    if (fn(arr[i]) < fn(pivot)) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // Recursively sort the left and right sub-arrays, and combine with the pivot
  return [...sortBy(left, fn), pivot, ...sortBy(right, fn)];
};

```
['JavaScript']