Following this problem some solutions use the following fact to find the reverse grouping where we have 1s first before 0s (10111000 -> 11110000).
"In fact, the sum of the final displacements (starting vs ending with all zeroes) will always equal num_zeroes * num_ones."
I can intuitively see how this would work however it's hard to see how this would hold in all cases.
An "inversion" is a pair that is out of order. In a string that contains only 0s and 1s, an inversion is a 0-1 pair where the 1 comes before the 0.
There are (num_zeros * num_ones) 0-1 pairs, regardless of what order the digits are in. If all the 1s are before all the 0s, though, then all of those pairs are inversions. If all the 0s come first, then none of them are inversions.
As long as you never swap identical elements (and what would be the point of that?), every swap of adjacent elements will change the order of exactly one 0-1 pair. The number of inversions will therefore go up or down by exactly one.
The number of adjacent swaps required to put all the zeros first is, therefore, the number of inversions. Each swap will fix one inversion, and you're done when there are none left.
The number of adjacent swaps required to put all the 1s first is num_zeros * num_ones - num_inversions. Each swap will create one new inversion, and you're done when all the 0-1 pairs are inversions.
