Sort By - Solution & Explanation

Problem Overview: You receive an array and a function fn. The task is to sort the array based on the value returned by applying fn to each element. Instead of comparing elements directly, you compare the computed keys produced by the function.

Approach 1: Using Built-in Sort with Key Function (Time: O(n log n), Space: O(1) to O(n))

The most direct solution relies on the language’s built-in sorting function. For each comparison, the algorithm applies fn(x) and fn(y) and orders the elements based on the returned values. Languages like Python provide a native key parameter, while JavaScript, Java, C++, and C# typically use a custom comparator that evaluates the function results during sorting.

The key idea is that the sorting algorithm handles ordering while your function defines the comparison rule. Internally, the algorithm performs O(n log n) comparisons, and each comparison may call the function. This makes the approach concise and easy to implement. For most interview scenarios and production code, this is the expected solution because it leverages optimized library sorting implementations.

This approach fits naturally into problems involving sorting and arrays, where you need to control ordering with a computed property.

Approach 2: Custom Sorting via a Map of Computed Keys (Time: O(n log n), Space: O(n))

Another option is to compute the key for every element once before sorting. Iterate through the array and store pairs like (fn(value), value) in a temporary structure such as a list or map. After that, sort the pairs using the precomputed key and extract the values in sorted order.

The key insight is avoiding repeated calls to fn. In some environments the sorting algorithm may evaluate the comparator many times, which can lead to redundant function executions. Precomputing the keys guarantees each element’s key is calculated exactly once. This pattern is sometimes called the “decorate-sort-undecorate” technique and commonly appears in custom comparator problems and hash map-based preprocessing.

The tradeoff is extra memory for storing the intermediate pairs. Time complexity remains O(n log n) because the array still needs to be sorted, but the function computation cost drops to O(n).

Recommended for interviews: The built-in sort with a key or comparator is what interviewers usually expect. It shows you understand how to customize sorting logic without reinventing the algorithm. Mentioning the precomputed-key optimization demonstrates deeper knowledge of how sorting repeatedly calls comparators and how to reduce redundant work.