Problem Description

You are given an array arr and a function fn. Your task is to return a new sorted array sortedArr where the elements are sorted based on the numeric values returned by applying fn to each element.

The sorting rules are:

• Apply the function fn to each element in the array to get a numeric value
• Sort the array elements in ascending order based on these numeric values
• If fn(a) returns a smaller number than fn(b), then a should come before b in the sorted array

Key constraints:

• The function fn only returns numbers
• The function fn will never return duplicate numbers for different elements in the same array (each element maps to a unique number)

For example, if you have an array [5, 4, 1, 2, 3] and a function fn = (x) => x, the sorted array would be [1, 2, 3, 4, 5]. If the function was fn = (x) => -x, the sorted array would be [5, 4, 3, 2, 1] because the negative values would reverse the order.

The solution uses JavaScript's built-in sort() method with a custom comparator function (a, b) => fn(a) - fn(b) to achieve the ascending order sorting based on the function's output values.

Intuition

The key insight is that we need to sort elements not by their own values, but by the values that the function fn produces when applied to them. This is a classic use case for custom sorting.

When we think about sorting, we typically compare two elements directly. But here, we need an intermediate step: first transform each element using fn, then compare those transformed values.

JavaScript's sort() method accepts a comparator function that determines the order of elements. The comparator takes two elements a and b and returns:

• A negative number if a should come before b
• A positive number if b should come before a
• Zero if they're equal

Since we want ascending order based on fn's output, we can directly use fn(a) - fn(b) as our comparator:

• If fn(a) < fn(b), the result is negative, placing a before b
• If fn(a) > fn(b), the result is positive, placing b before a

This elegantly handles the transformation and comparison in a single expression. The guarantee that fn never produces duplicate values for a given array means we don't need to worry about handling ties or maintaining stable sort order for equal values.

The beauty of this approach is its simplicity - we let the built-in sort method handle all the complexity of the sorting algorithm itself, while we just provide the logic for comparing elements based on their transformed values.

Solution Approach

The implementation uses JavaScript's built-in Array.sort() method with a custom comparator function. Let's walk through how this works:

Step 1: Understanding the Sort Method

The sort() method modifies the array in-place and accepts a comparator function that defines the sorting logic. The comparator receives two elements at a time and determines their relative order.

Step 2: Creating the Comparator Function

The comparator (a, b) => fn(a) - fn(b) works as follows:

• Takes two elements a and b from the array
• Applies the transformation function fn to both elements
• Returns the difference fn(a) - fn(b)

Step 3: How the Sorting Works

When sort() executes with our comparator:

1. For any two elements being compared, it calls fn(a) and fn(b) to get their numeric values
2. The subtraction fn(a) - fn(b) produces:
   • A negative value when fn(a) < fn(b) → a is placed before b
   • A positive value when fn(a) > fn(b) → b is placed before a
   • Zero when fn(a) === fn(b) → order remains unchanged (though this won't happen per problem constraints)

Example Walkthrough:

If arr = [3, 1, 2] and fn = (x) => x * x:

• Comparing 3 and 1: fn(3) - fn(1) = 9 - 1 = 8 (positive, so 1 comes before 3)
• Comparing 1 and 2: fn(1) - fn(2) = 1 - 4 = -3 (negative, so 1 comes before 2)
• Comparing 3 and 2: fn(3) - fn(2) = 9 - 4 = 5 (positive, so 2 comes before 3)
• Result: [1, 2, 3] (sorted by square values: 1, 4, 9)

The solution is efficient and concise, leveraging the language's built-in sorting capabilities while providing custom comparison logic through the function composition.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• arr = [3, -2, 1, -4]
• fn = (x) => x * x (squares each number)

Step 1: Understand what fn does to each element

• fn(3) = 9
• fn(-2) = 4
• fn(1) = 1
• fn(-4) = 16

Step 2: Apply the sort with comparator (a, b) => fn(a) - fn(b)

The sort method will compare pairs of elements. Let's trace through some comparisons:

First comparison: 3 and -2

• fn(3) - fn(-2) = 9 - 4 = 5 (positive)
• Since the result is positive, -2 should come before 3

Second comparison: -2 and 1

• fn(-2) - fn(1) = 4 - 1 = 3 (positive)
• Since the result is positive, 1 should come before -2

Third comparison: 1 and -4

• fn(1) - fn(-4) = 1 - 16 = -15 (negative)
• Since the result is negative, 1 should come before -4

Step 3: Build the final sorted order

Based on the squared values:

• 1 has the smallest squared value (1)
• -2 has the next smallest squared value (4)
• 3 has the third smallest squared value (9)
• -4 has the largest squared value (16)

Final Result: [1, -2, 3, -4]

This demonstrates how elements are sorted not by their original values, but by the values produced when fn is applied to them. The comparator fn(a) - fn(b) ensures ascending order based on the transformed values.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The sortBy function uses JavaScript's built-in sort() method with a custom comparator function. The time complexity of the sort operation depends on the underlying sorting algorithm implementation, which in most JavaScript engines (like V8) is typically Timsort or a variation of quicksort. These algorithms have an average and worst-case time complexity of O(n log n), where n is the number of elements in the array.

Additionally, the comparator function fn is called O(n log n) times during the sorting process. If we assume fn has a time complexity of O(f), the overall time complexity becomes O(n log n × f). When fn is O(1) (constant time), the total complexity remains O(n log n).

Space Complexity: O(n)

The space complexity depends on the sorting algorithm implementation:

• The sort() method in JavaScript typically uses O(log n) auxiliary space for the recursive call stack in algorithms like quicksort or Timsort
• However, since sort() may create temporary arrays during the sorting process (especially in Timsort for merging), the worst-case space complexity can be O(n)
• The function returns the sorted array in-place (modifying the original array), so no additional O(n) space is needed for the output

Therefore, the overall space complexity is O(n) in the worst case, though it could be O(log n) in practice depending on the specific implementation and input characteristics.

Common Pitfalls

1. Modifying the Original Array Instead of Creating a New One

A frequent mistake is using JavaScript's arr.sort() directly, which modifies the original array in-place rather than creating a new sorted array as required by the problem.

Incorrect approach:

function sortBy(arr, fn) {
    return arr.sort((a, b) => fn(a) - fn(b)); // Modifies original array!
}

Correct approach:

function sortBy(arr, fn) {
    return [...arr].sort((a, b) => fn(a) - fn(b)); // Creates a copy first
}
// or
function sortBy(arr, fn) {
    return arr.slice().sort((a, b) => fn(a) - fn(b)); // Also creates a copy
}

2. Caching Function Results for Performance

When fn is computationally expensive, the sort comparator calls it multiple times for the same elements during sorting (approximately O(n log n) times per element). This can lead to performance issues.

Inefficient approach:

function sortBy(arr, fn) {
    return [...arr].sort((a, b) => fn(a) - fn(b)); // fn called multiple times per element
}

Optimized approach using Schwartzian Transform:

function sortBy(arr, fn) {
    return arr
        .map(item => [item, fn(item)])  // Cache fn results
        .sort((a, b) => a[1] - b[1])     // Sort by cached values
        .map(pair => pair[0]);           // Extract original elements
}

3. Handling Non-Numeric Return Values

While the problem states fn only returns numbers, defensive programming suggests validating this assumption to prevent unexpected behavior.

Vulnerable approach:

function sortBy(arr, fn) {
    return [...arr].sort((a, b) => fn(a) - fn(b)); // Assumes fn always returns numbers
}

Defensive approach:

function sortBy(arr, fn) {
    return [...arr].sort((a, b) => {
        const valA = fn(a);
        const valB = fn(b);
        if (typeof valA !== 'number' || typeof valB !== 'number') {
            throw new Error('Function must return numeric values');
        }
        return valA - valB;
    });
}

4. Language-Specific Sort Stability Concerns

Different programming languages handle stable sorting differently. While modern JavaScript (ES2019+) guarantees stable sorting, older versions don't. Python's sorted() is always stable, but this distinction matters when migrating code between languages or dealing with legacy environments.

Cross-language consideration:

• Python's sorted(arr, key=fn) maintains relative order for equal elements
• Pre-ES2019 JavaScript might not preserve original order for equal fn values
• Though the problem states fn returns unique values, this becomes important when requirements change