MAYBE
Input TRS:
      1: average(x,y) -> if(ge(x,y),x,y)
      2: if(true(),x,y) -> averIter(y,x,y)
      3: if(false(),x,y) -> averIter(x,y,x)
      4: averIter(x,y,z) -> ifIter(ge(x,y),x,y,z)
      5: ifIter(true(),x,y,z) -> z
      6: ifIter(false(),x,y,z) -> averIter(plus(x,s(s(s(0())))),plus(y,s(0())),plus(z,s(0())))
      7: append(nil(),y) -> y
      8: append(cons(n,x),y) -> cons(n,app(x,y))
      9: low(n,nil()) -> nil()
      10: low(n,cons(m,x)) -> if_low(ge(m,n),n,cons(m,x))
      11: if_low(false(),n,cons(m,x)) -> cons(m,low(n,x))
      12: if_low(true(),n,cons(m,x)) -> low(n,x)
      13: high(n,nil()) -> nil()
      14: high(n,cons(m,x)) -> if_high(ge(m,n),n,cons(m,x))
      15: if_high(false(),n,cons(m,x)) -> high(n,x)
      16: if_high(true(),n,cons(m,x)) -> cons(average(m,m),high(n,x))
      17: quicksort(x) -> ifquick(isempty(x),x)
      18: ifquick(true(),x) -> nil()
      19: ifquick(false(),x) -> append(quicksort(low(head(x),tail(x))),cons(tail(x),quicksort(high(head(x),tail(x)))))
      20: plus(0(),y) -> y
      21: plus(s(x),y) -> s(plus(x,y))
      22: isempty(nil()) -> true()
      23: isempty(cons(n,x)) -> false()
      24: head(nil()) -> error()
      25: head(cons(n,x)) -> n
      26: tail(nil()) -> nil()
      27: tail(cons(n,x)) -> x
      28: ge(x,0()) -> true()
      29: ge(0(),s(y)) -> false()
      30: ge(s(x),s(y)) -> ge(x,y)
      31: a() -> b()
      32: a() -> c()
Number of strict rules: 32
Direct POLO(bPol) ... failed.
Uncurrying ... failed.
Dependency Pairs:
     #1: #if(true(),x,y) -> #averIter(y,x,y)
     #2: #ifIter(false(),x,y,z) -> #averIter(plus(x,s(s(s(0())))),plus(y,s(0())),plus(z,s(0())))
     #3: #ifIter(false(),x,y,z) -> #plus(x,s(s(s(0()))))
     #4: #ifIter(false(),x,y,z) -> #plus(y,s(0()))
     #5: #ifIter(false(),x,y,z) -> #plus(z,s(0()))
     #6: #if_low(false(),n,cons(m,x)) -> #low(n,x)
     #7: #if_low(true(),n,cons(m,x)) -> #low(n,x)
     #8: #high(n,cons(m,x)) -> #if_high(ge(m,n),n,cons(m,x))
     #9: #high(n,cons(m,x)) -> #ge(m,n)
     #10: #ge(s(x),s(y)) -> #ge(x,y)
     #11: #low(n,cons(m,x)) -> #if_low(ge(m,n),n,cons(m,x))
     #12: #low(n,cons(m,x)) -> #ge(m,n)
     #13: #quicksort(x) -> #ifquick(isempty(x),x)
     #14: #quicksort(x) -> #isempty(x)
     #15: #ifquick(false(),x) -> #append(quicksort(low(head(x),tail(x))),cons(tail(x),quicksort(high(head(x),tail(x)))))
     #16: #ifquick(false(),x) -> #quicksort(low(head(x),tail(x)))
     #17: #ifquick(false(),x) -> #low(head(x),tail(x))
     #18: #ifquick(false(),x) -> #head(x)
     #19: #ifquick(false(),x) -> #tail(x)
     #20: #ifquick(false(),x) -> #tail(x)
     #21: #ifquick(false(),x) -> #quicksort(high(head(x),tail(x)))
     #22: #ifquick(false(),x) -> #high(head(x),tail(x))
     #23: #ifquick(false(),x) -> #head(x)
     #24: #ifquick(false(),x) -> #tail(x)
     #25: #plus(s(x),y) -> #plus(x,y)
     #26: #if_high(true(),n,cons(m,x)) -> #average(m,m)
     #27: #if_high(true(),n,cons(m,x)) -> #high(n,x)
     #28: #if(false(),x,y) -> #averIter(x,y,x)
     #29: #average(x,y) -> #if(ge(x,y),x,y)
     #30: #average(x,y) -> #ge(x,y)
     #31: #if_high(false(),n,cons(m,x)) -> #high(n,x)
     #32: #averIter(x,y,z) -> #ifIter(ge(x,y),x,y,z)
     #33: #averIter(x,y,z) -> #ge(x,y)
Number of SCCs: 6, DPs: 13
  SCC { #25 }
POLO(Sum)... succeeded.
      a 	w: 0
      isempty	w: 0
      s 	w: x1 + 1
      #append	w: 0
      b 	w: 0
      average	w: 0
      if_high	w: 0
      ifIter	w: 0
      #plus	w: x1
      #isempty	w: 0
      #quicksort	w: 0
      #high	w: 0
      #ifquick	w: 0
      false	w: 0
      #head	w: 0
      #ge	w: 0
      ifquick	w: 0
      #if_high	w: 0
      c 	w: 0
      quicksort	w: 0
      true	w: 0
      tail	w: 0
      #ifIter	w: 0
      error	w: 0
      append	w: 0
      if	w: 0
      0 	w: 0
      high	w: 0
      ge	w: 0
      nil	w: 0
      #tail	w: 0
      #average	w: 0
      low	w: 0
      plus	w: 0
      head	w: 0
      cons	w: 0
      #if	w: 0
      #a 	w: 0
      averIter	w: 0
      if_low	w: 0
      #averIter	w: 0
      #if_low	w: 0
      #low	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #25
Number of SCCs: 5, DPs: 12
  SCC { #10 }
POLO(Sum)... succeeded.
      a 	w: 0
      isempty	w: 0
      s 	w: x1 + 1
      #append	w: 0
      b 	w: 0
      average	w: 0
      if_high	w: 0
      ifIter	w: 0
      #plus	w: 0
      #isempty	w: 0
      #quicksort	w: 0
      #high	w: 0
      #ifquick	w: 0
      false	w: 0
      #head	w: 0
      #ge	w: x2
      ifquick	w: 0
      #if_high	w: 0
      c 	w: 0
      quicksort	w: 0
      true	w: 0
      tail	w: 0
      #ifIter	w: 0
      error	w: 0
      append	w: 0
      if	w: 0
      0 	w: 0
      high	w: 0
      ge	w: 0
      nil	w: 0
      #tail	w: 0
      #average	w: 0
      low	w: 0
      plus	w: 0
      head	w: 0
      cons	w: 0
      #if	w: 0
      #a 	w: 0
      averIter	w: 0
      if_low	w: 0
      #averIter	w: 0
      #if_low	w: 0
      #low	w: 0
      app	w: 0
    USABLE RULES: { }
    Removed DPs: #10
Number of SCCs: 4, DPs: 11
  SCC { #13 #16 #21 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... succeeded.
      a 	w: 0
      isempty	w: max(x1 - 1432, 0)
      s 	w: 1
      #append	w: 0
      b 	w: 0
      average	w: max(x1 + 1, x2, 0)
      if_high	w: max(x3, 0)
      ifIter	w: max(x1, 0)
      #plus	w: max(x1 - 1, 0)
      #isempty	w: max(x1 - 1, 0)
      #quicksort	w: max(x1 - 842, 0)
      #high	w: 0
      #ifquick	w: max(x1 - 1, x2 - 843, 0)
      false	w: 16909
      #head	w: max(x1 - 1, 0)
      #ge	w: 0
      ifquick	w: max(x1 - 1, 0)
      #if_high	w: 0
      c 	w: 0
      quicksort	w: 0
      true	w: 0
      tail	w: max(x1 - 843, 0)
      #ifIter	w: 0
      error	w: 0
      append	w: 0
      if	w: max(x2 + 2, 0)
      0 	w: 1
      high	w: max(x2, 0)
      ge	w: 0
      nil	w: 0
      #tail	w: 0
      #average	w: 0
      low	w: max(x2 + 841, 0)
      plus	w: max(x2 + 1, 0)
      head	w: max(x1 - 1, 0)
      cons	w: max(x2 + 18341, 0)
      #if	w: 0
      #a 	w: 0
      averIter	w: max(x2 + 18590, x3, 0)
      if_low	w: max(x3 + 841, 0)
      #averIter	w: 0
      #if_low	w: 0
      #low	w: 0
      app	w: max(x1 - 1, 0)
    USABLE RULES: { 9..16 22..24 26 27 }
    Removed DPs: #16 #21
Number of SCCs: 3, DPs: 8
  SCC { #8 #27 #31 }
POLO(Sum)... succeeded.
      a 	w: 0
      isempty	w: 0
      s 	w: x1 + 1
      #append	w: 0
      b 	w: 0
      average	w: 1
      if_high	w: 3
      ifIter	w: x3 + 4
      #plus	w: 0
      #isempty	w: 0
      #quicksort	w: 1
      #high	w: x2 + 2
      #ifquick	w: 0
      false	w: 1
      #head	w: 0
      #ge	w: 0
      ifquick	w: 0
      #if_high	w: x3
      c 	w: 0
      quicksort	w: 0
      true	w: 1
      tail	w: 1
      #ifIter	w: 0
      error	w: 2
      append	w: 0
      if	w: x2 + 2
      0 	w: 1
      high	w: 1
      ge	w: x1 + 3
      nil	w: 3
      #tail	w: 0
      #average	w: 0
      low	w: 2
      plus	w: x2
      head	w: 1
      cons	w: x2 + 3
      #if	w: 0
      #a 	w: 0
      averIter	w: x3 + 3
      if_low	w: x1 + x2
      #averIter	w: 0
      #if_low	w: 0
      #low	w: 0
      app	w: 0
    USABLE RULES: { 28..30 }
    Removed DPs: #8 #27 #31
Number of SCCs: 2, DPs: 5
  SCC { #6 #7 #11 }
POLO(Sum)... succeeded.
      a 	w: 0
      isempty	w: 0
      s 	w: x1 + 1
      #append	w: 0
      b 	w: 0
      average	w: 1
      if_high	w: 3027
      ifIter	w: x3 + 4
      #plus	w: 0
      #isempty	w: 0
      #quicksort	w: 1
      #high	w: 2
      #ifquick	w: 0
      false	w: 1
      #head	w: 0
      #ge	w: 0
      ifquick	w: 0
      #if_high	w: 0
      c 	w: 0
      quicksort	w: 0
      true	w: 1
      tail	w: 1
      #ifIter	w: 0
      error	w: 2
      append	w: 0
      if	w: x2 + 2
      0 	w: 1
      high	w: 2
      ge	w: x1 + 3
      nil	w: 3
      #tail	w: 0
      #average	w: 0
      low	w: 2
      plus	w: x2
      head	w: 1
      cons	w: x2 + 3026
      #if	w: 0
      #a 	w: 0
      averIter	w: x3 + 3
      if_low	w: x1 + x2
      #averIter	w: 0
      #if_low	w: x3
      #low	w: x2 + 3025
      app	w: 0
    USABLE RULES: { 28..30 }
    Removed DPs: #6 #7 #11
Number of SCCs: 1, DPs: 2
  SCC { #2 #32 }
POLO(Sum)... POLO(max)... QLPOS... POLO(mSum)... QWPOpS(mSum)... Mat2b... failed.
Finding a loop...  failed.