Es raro, yo tengo una implementación que tiene diferencias. Los siguientes son tiempos de encode+decode.
Con "El Quijote":
$ time ./pr2ej3DT
real 0m0,565s
user 0m0,544s
sys 0m0,008s
$ time ./pr2ej3String
real 0m2,203s
user 0m1,906s
sys 0m0,274s
Con "La Guerra y la Paz":
$ time ./pr2ej3DT
real 0m1,763s
user 0m1,704s
sys 0m0,046s
$ time ./pr2ej3String
real 0m6,718s
user 0m6,055s
sys 0m0,661s
Quizás en algún punto no estés cortando la fusión por uso incorrecto de alguna función? Definiste encode de forma composicional?