Sort an array by the number of set bits

Easy

Problem

Sort the integers in decreasing order of how many 1 bits their binary form has. Numbers with the same count keep their original relative order (a stable sort).

Example 1

Input:  [5, 2, 3, 9, 4, 6, 7, 15, 32]
Output: [15, 7, 5, 3, 9, 6, 2, 4, 32]

Also asked as: Sort array according to count of set bits

Test cases

Case 1

Input:    [5,2,3,9,4,6,7,15,32]
Expected: [15,7,5,3,9,6,2,4,32]

Case 2

Input:    [1,2,3,4,5,6]
Expected: [3,5,6,1,2,4]

Case 3

Input:    [8]
Expected: [8]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stable sort with a popcount comparator

Time O(n log n)Space O(n)

Sort descending by popcount; ties keep their original order (use a stable sort or a secondary key).

const popcount = (x) => { let c = 0; while (x) { x &= x - 1; c++; } return c; };
function sortBySetBits(a) {
return a
.map((v, i) => [v, i, popcount(v)])
.sort((p, q) => q[2] - p[2] || p[1] - q[1])
.map((t) => t[0]);
}