#Pyth, 29 bytes

This is a direct translation of my [CJam answe][1]r in Pyth

    oc/|$Y.append(N)$YN/zNo_/zZSz

[Try it online here][2]


----------
There is a rather long story behind this solution and @isaacg helped me a lot in understanding this new language.

Ideally this is the exact word to word translation of my CJam code (**17 bytes**):

    oc/~kNN/zNo_/zZSz

which means:

    o         order_by(lambda N:
     c                 div(
      /                    count(
       ~kN                       k+=N,                #Update k (initially ""), add N
       N                         N),                  #Count N in updated k
      /zN                  count(z, N)),
     o                 order_by(lambda Z:
      _                         neg(
       /zZ                          count(z, Z)),
      Sz                        sorted(z)))

But sadly Python does not return anything in a `+=` call, so that was not a valid Python code, thus an invalid Pyth code too as in Pyth, a lambda can only be a return statement.

Then I looked into various methods and finally found that Python's `list.append` returns a `None` value, which I can use. Making the code to be (**19 bytes**):

    oc/|aYNYN/zNo_/zZSz

which means:

    o         order_by(lambda N:
     c                 div(
      /                    count(
       |aYN                      (Y.append(N) or
        Y                         Y)                 #Update Y (initially []), append N
       N                         N),                 #Count N in updated Y
      /zN                  count(z, N)),
     o                 order_by(lambda Z:
      _                         neg(
       /zZ                          count(z, Z)),
      Sz                        sorted(z)))

But sadly, support of `a` (append) was removed from Pyth and the version which do has the support, does not have the support for `o`.

*Update : `a` support has been added back in Pyth now so the above 19 byte code will work in the online compiler. But since this is a new feature which was added after the OP, I am not putting it up as my score and letting the 29 byte code as my solution.*

Therefore I had to rely on raw Python in that case, making the code to be

    o         order_by(lambda N:
     c                 div(
      /                    count(
       |$Y.append(N)$            (Y.append(N) or
        Y                         Y)                 #Update Y (initially []), append N
       N                         N),                 #Count N in updated Y
      /zN                  count(z, N)),
     o                 order_by(lambda Z:
      _                         neg(
       /zZ                          count(z, Z)),
      Sz                        sorted(z)))


  [1]: http://codegolf.stackexchange.com/a/40914/31414
  [2]: http://isaacg.scripts.mit.edu/pyth/index.py