Sort Array By Absolute Value - Solution & Explanation

Problem Overview: Given an integer array, reorder the elements so they are sorted by their absolute values. The comparison is performed using abs(x) instead of the raw value. Negative and positive numbers with the same magnitude should maintain the correct relative ordering defined by the comparator.

Approach 1: Custom Sorting with Absolute Comparator (O(n log n) time, O(1)–O(n) space)

The most direct solution uses a sorting algorithm with a custom comparator. Instead of comparing two numbers directly, the comparator evaluates abs(a) and abs(b). Most languages support this through a custom comparison function or a key extractor such as key=abs in Python. The sorting algorithm repeatedly compares elements using their absolute values and reorders the array accordingly. Time complexity is O(n log n) because it relies on comparison-based sorting. Space complexity ranges from O(1) to O(n) depending on the language’s sort implementation.

This method works for all inputs and requires minimal code. It is also the approach used in most production code because modern sorting implementations are highly optimized. The logic remains simple: iterate through the array implicitly via the sorting routine, compare absolute values, and swap elements when needed. This approach is closely tied to the fundamentals of sorting and basic array manipulation.

Approach 2: Bucket by Absolute Value (O(n + k) time, O(k) space)

If the value range is small, you can group numbers by their absolute value using buckets or a hash map. First iterate through the array and compute abs(x) for each element. Store the element in a bucket keyed by that absolute value. Then iterate through the buckets in ascending key order and append elements back into the result array. The iteration step costs O(n), and ordering the buckets costs up to O(k) where k is the range of absolute values.

This method avoids comparison-based sorting and can be faster when the absolute value range is small relative to the input size. It relies on simple math operations and sequential iteration. The tradeoff is additional memory for buckets and slightly more implementation complexity.

Recommended for interviews: Custom sorting with an absolute-value comparator is the expected solution. It demonstrates clear understanding of sorting mechanics and comparator design while keeping the implementation concise. Mentioning the bucket strategy shows deeper algorithmic thinking, but the O(n log n) custom sort is typically what interviewers want to see first.