Mathematica, 123 119119 118 bytes
f=FromCharacterCode[s=SortBy;#&@@@s[Join@@(s[Tally@ToCharacterCode@#,-Last@#&]/.{x_,n_}:>({x,#/n}&/@Range@n&~Array~n)),{Last}]]&
Defines a named function f
. Ungolfed:
f = FromCharacterCode[
s = SortBy;
# & @@@ s[
Join @@ (
s[
Tally@ToCharacterCode@#,
-Last@# &
] /. {x_, n_} :> ({x, #/n} & /@ Range@n&~Array~n)
),
{Last}
]
] &
Using built-in rational types seemed like a good idea for this. Of course, this is nowhere near CJam. Basically, I'm representing the grid shown in the challenge as a list of pairs. The first thing in the pair is the character code, the second is it's position as a fraction less than or equal to 1 (the final column being 1). Having made sure that the individual characters are already in the right order, I just need to sort this stably by said fraction to get the desired result.