Sort By

Problem Description

Given an array arr and a function fn, return a sorted array sortedArr. You can assume fn only returns numbers and those numbers determine the sort order of sortedArr. sortedArr must be sorted in ascending order by fn output. You may assume that fn will never duplicate numbers for a given array.

Key Insights

• The function fn is used to determine the sorting criteria for the elements in arr.
• The sorting must be performed in ascending order based on the output of the fn function.
• The input can be a variety of types (numbers, objects, arrays), as long as the output of fn is a number.
• The constraints allow for large arrays, so efficiency in sorting is essential.

Space and Time Complexity

Time Complexity: O(n log n) - This is due to the sorting algorithm typically used (like Timsort in Python and JavaScript). Space Complexity: O(n) - This may be required for storing the sorted output.

Solution

To solve this problem, we can use a sorting algorithm that allows us to specify a sorting key. The key will be provided by the function fn. We will apply this function to each element in the array to obtain the corresponding sorting values. The built-in sort method will then arrange the elements based on these values in ascending order.

In terms of data structures, we are primarily working with arrays (or lists) and using a sorting algorithm that typically employs a divide-and-conquer approach.

Code Solutions