Sort Integers by The Number of 1 Bits - Solution & Explanation

Problem Overview: Given an array of integers, sort the numbers based on how many 1 bits appear in their binary representation. If two numbers have the same number of set bits, order them by their numeric value.

The task combines Bit Manipulation with Sorting. The core operation is computing the popcount (number of set bits) for each integer and using it as the primary sorting key.

Approach 1: Sorting with Custom Key Function (O(n log n) time, O(1) extra space)

Sort the array using a custom comparator or key function. The key returns a pair: (bitCount(x), x). The first element sorts numbers by the number of set bits. The second element ensures values with the same bit count are ordered numerically. Most languages expose built-in popcount utilities such as bin(x).count('1') in Python, Integer.bitCount() in Java, or __builtin_popcount() in C++. The sorting algorithm handles the ordering once the key is defined. Time complexity is O(n log n) due to sorting, while space complexity is O(1) or O(log n) depending on the sorting implementation.

Approach 2: Counting Bits and Sorting (O(n log n) time, O(n) space)

First compute the bit count for every number and store it alongside the value, typically as pairs like (bitCount, value). Bit counts can be calculated using Kernighan’s algorithm, built-in popcount functions, or simple bit shifting. After building this list, sort it using the pair structure so that the array is ordered by bit count first and number second. Finally extract the sorted numbers back into the result array. The preprocessing pass takes O(n * B) where B is the number of bits (at most 32 for typical integers), followed by sorting in O(n log n). Space complexity becomes O(n) due to the auxiliary array.

Both approaches rely on the same insight: treat the bit count as the primary sorting metric and the integer value as the tie breaker. The problem mainly tests familiarity with Array handling and popcount operations.

Recommended for interviews: The custom key sorting approach is the expected solution. It is concise, leverages built-in popcount functions, and clearly expresses the intended ordering rule. Mentioning how to compute set bits (for example with Kernighan’s trick) shows deeper understanding of bit manipulation even if the implementation uses a built-in method.