YES

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)))

linear polynomial interpretations on N:

  qsort_A(x1) = x1
  qsort#_A(x1) = x1 + 2
  nil_A = 1
  nil#_A = 2
  ._A(x1,x2) = x1 + 2
  .#_A(x1,x2) = 0
  ++_A(x1,x2) = x1
  ++#_A(x1,x2) = 1
  lowers_A(x1,x2) = 1
  lowers#_A(x1,x2) = x1 + 1
  greaters_A(x1,x2) = x1 + 1
  greaters#_A(x1,x2) = 3
  if_A(x1,x2,x3) = x1
  if#_A(x1,x2,x3) = 0
  <=_A(x1,x2) = 1
  <=#_A(x1,x2) = 0

precedence:

  qsort > greaters > nil > lowers > . = if = <= > ++