Abstract the (duplicate?) behavior between "sort" and "replace"
I think the later versions are unnecessarily complicated and verbose.

My first idea was to just concatenate the splitted list parts in replace-all – for you can do (concatenate 'string seqs ... ) – but that may not be very efficient.

You can use map or loop for replace-all. This map version works for lists too:


(defun replace-all (seq from to)
  (map (type-of seq) (lambda (char) (if (equal from char) to char)) seq))


Naming things clearly can sometimes be hard, and I think sometimes being terse helps readability more than being too-explicit-and-specific. That if statement above could need some better naming of things...

There is an utility library called split-sequence, that has many useful options, like


remove empty subsequences
only split count times
return the index position (useful for further processing)


I'm still learning Lisp, so you may want to hear see other answers also.