[sonoffett]

quicksort is O(n^2) which is definitely not the "best big-O" for sorting.

[pkaye]

Quicksort is O(n log n) average and O(n^2) worst case. Heapsort is O(n log n) for both average and worst case.

[Jiig]

Its worst case is O(n^2) sure, so heap sort would be better if you know that your data would hit the worst case scenario of quick sort every time.

[sonoffett]

"how do you count the bits most efficiently?"

What does this even mean?

[dekhn]

If you have a collection of data, and you want to know the number of 1 bits, and you want to do it with a minimum of resources... what is the process?

For example, standard bit-shifting and masking the lowest bit to set a counter is one way to do this. Possibly there are other, faster ways, such as using a lookup table (a byte or more can be "counted" at a time). Of course, because so many people were doing this, intel added a popcnt instruction which probably is more efficient (faster) than either of the above, at the expense of more CPU real estate, heat, etc.

Turns out counting 1 bits in a dataset is a super-important problem that shows up in a lot of situations.

[UK-AL]

What i think he means is counting the amount of set(1) bits in the array,

[sonoffett]

Thanks, the question makes more sense now :)

[dekhn]

quicksort is O(nlogn) average case, and O(n2) on already sorted arrays.

[bvinc]

Just a nitpick: There are versions of quicksort that perform well, O(n*log n), on already sorted data. But there is always some worst case scenario where it can be O(n^2).