R
↳Dependency Pair Analysis
QSORT(.(x, y)) > QSORT(lowers(x, y))
QSORT(.(x, y)) > LOWERS(x, y)
QSORT(.(x, y)) > QSORT(greaters(x, y))
QSORT(.(x, y)) > GREATERS(x, y)
LOWERS(x, .(y, z)) > LOWERS(x, z)
GREATERS(x, .(y, z)) > GREATERS(x, z)
R
↳DPs
→DP Problem 1
↳Usable Rules (Innermost)
→DP Problem 2
↳UsableRules
LOWERS(x, .(y, z)) > LOWERS(x, z)
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)))
innermost
R
↳DPs
→DP Problem 1
↳UsableRules
→DP Problem 3
↳SizeChange Principle
→DP Problem 2
↳UsableRules
LOWERS(x, .(y, z)) > LOWERS(x, z)
none
innermost


trivial
.(x_{1}, x_{2}) > .(x_{1}, x_{2})
R
↳DPs
→DP Problem 1
↳UsableRules
→DP Problem 2
↳Usable Rules (Innermost)
GREATERS(x, .(y, z)) > GREATERS(x, z)
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)))
innermost
R
↳DPs
→DP Problem 1
↳UsableRules
→DP Problem 2
↳UsableRules
→DP Problem 4
↳SizeChange Principle
GREATERS(x, .(y, z)) > GREATERS(x, z)
none
innermost


trivial
.(x_{1}, x_{2}) > .(x_{1}, x_{2})