MAYBE

We are left with following problem, upon which TcT provides the
certificate MAYBE.

Strict Trs:
  { qsort(nil()) -> nil()
  , qsort(.(x, y)) ->
    ++(qsort(lowers(x, y)), .(x, qsort(greaters(x, y))))
  , lowers(x, nil()) -> nil()
  , lowers(x, .(y, z)) ->
    if(<=(y, x), .(y, lowers(x, z)), lowers(x, z))
  , greaters(x, nil()) -> nil()
  , greaters(x, .(y, z)) ->
    if(<=(y, x), greaters(x, z), .(y, greaters(x, z))) }
Obligation:
  innermost runtime complexity
Answer:
  MAYBE

The input cannot be shown compatible

Arrrr..