a) Where you say "mappend [do _]", you can just say "apply + nil". Actually, I've been using "apply join", but it turns out that performs much worse:

  arc> (time10:mappend idfn (n-of 10000 nil))
  time: 468 msec.
  nil
  arc> (time10:apply join (n-of 10000 nil))
  time: 50454 msec.
  nil
  arc> (time10:apply + nil (n-of 10000 nil))
  time: 437 msec.
  nil

c) Not that it'll really save anything when it comes to the overall computational complexity, but this version of list length comparison will only traverse the lists up to the end of the shorter one:

  (def longer-list (a b)
    (if a
      (if b
        (longer-list cdr.a cdr.b)
        t)
      nil))

e) There's no need to call 'testify.

After incorporating a bunch of this feedback--I didn't pit '< against '> --the code might look like this:

  (def sort-by-commonest5r1 (seq)
    (apply + nil
      (sort longer-list
        ( (afn (xs cxs ys)
            (if xs
              (withs (x car.xs
                      f [isnt _ x]
                      r (reclist [if (f:car _) _] xs)
                      cr len.r)
                (self r cr (cons (firstn (- cxs cr) xs) ys)))
              ys))
          (sort > seq) len.seq nil))))

  (def sort-by-commonest5r2 (seq)
    (apply join
      (sort longer-list
        ( (afn (rest bins)
            (iflet (sample . rest) rest
              ( (rfn self2 (bin rest)
                  (if rest
                    (let first car.rest
                      (if (is sample first)
                        (self2 (cons first bin) cdr.rest)
                        (self rest (cons bin bins))))
                    (cons bin bins)))
                list.sample rest)
              bins))
          (sort > seq) nil))))

  arc> (time:repeat 100 sort-by-commonest5r1.data)
  time: 18390 msec.
  nil
  arc> (time:repeat 100 sort-by-commonest5r2.data)
  time: 20437 msec.
  nil
  arc> (time:repeat 100 sort-by-commonest5.data)
  time: 19594 msec.
  nil