MAYBE
* Step 1: Failure MAYBE
  + Considered Problem:
      - Strict TRS:
          goal(xs) -> mergesort(xs)
          merge(Cons(x,xs),Nil()) -> Cons(x,xs)
          merge(Cons(x',xs'),Cons(x,xs)) -> merge[Ite](<=(x',x),Cons(x',xs'),Cons(x,xs))
          merge(Nil(),xs2) -> xs2
          mergesort(Cons(x,Nil())) -> Cons(x,Nil())
          mergesort(Cons(x',Cons(x,xs))) -> splitmerge(Cons(x',Cons(x,xs)),Nil(),Nil())
          mergesort(Nil()) -> Nil()
          notEmpty(Cons(x,xs)) -> True()
          notEmpty(Nil()) -> False()
          splitmerge(Cons(x,xs),xs1,xs2) -> splitmerge(xs,Cons(x,xs2),xs1)
          splitmerge(Nil(),xs1,xs2) -> merge(mergesort(xs1),mergesort(xs2))
      - Weak TRS:
          <=(0(),y) -> True()
          <=(S(x),0()) -> False()
          <=(S(x),S(y)) -> <=(x,y)
          merge[Ite](False(),xs1,Cons(x,xs)) -> Cons(x,merge(xs1,xs))
          merge[Ite](True(),Cons(x,xs),xs2) -> Cons(x,merge(xs,xs2))
      - Signature:
          {<=/2,goal/1,merge/2,merge[Ite]/3,mergesort/1,notEmpty/1,splitmerge/3} / {0/0,Cons/2,False/0,Nil/0,S/1
          ,True/0}
      - Obligation:
          innermost runtime complexity wrt. defined symbols {<=,goal,merge,merge[Ite],mergesort,notEmpty
          ,splitmerge} and constructors {0,Cons,False,Nil,S,True}
  + Applied Processor:
      NaturalPI {shape = Mixed 3, restrict = NoRestrict, uargs = UArgs, urules = URules, selector = Nothing}
  + Details:
      Incompatible
MAYBE