Function that returns the union(in alphabetic order) of two sets in Lisp

The procedure below takes two lists and returns their union as an ordered list.

(defun stable-union (lst1 lst2)
  (cond ((null lst1) lst2)
        ((null lst2) lst1)
        ((and (null lst1) (null lst2)) nil)
        (t
         (let ((el1 (car lst1))
               (el2 (car lst2)))
           (cond ((string= el1 el2)
                  (cons el1
                     (stable-union (cdr lst1)  (cdr lst2))))
                  ((string< el1 el2)
                   (cons el1
                         (stable-union (cdr lst1)  lst2)))
                  (t
                   (cons el2
                         (stable-union lst1 (cdr lst2)))))))))

It works for some examples and fails for others. For example:

STABLE-UNION: (STABLE-UNION '(A B C) '(B A D)) failed: 
Expected (A B C D) but saw (A B A C D)
STABLE-UNION: (STABLE-UNION '(A B C) '(A D B E)) failed: 
Expected (A B C D E) but saw (A B C D B E)
STABLE-UNION: (STABLE-UNION '(C B A) '(A E B D)) failed: 
Expected (C B A E D) but saw (A C B A E B D)

Can you guide me as to where I am making mistakes in my code? Thank you so much.

Solution

The above function works only for lists that are composed by symbols already lexicographically ordered. So, for instance, it works correctly for '(A B C) '(A B D), but not for '(A B C) '(B A D).

There are several ways of correcting it. The simplest one is to call it by sorting (with stable-sort) the two arguments, for instance:

(defun stable-union-general (lst1 lst2)
   (stable-union (stable-sort lst1 #'string<) (stable-sort lst2 #'string<)))

(stable-union-general '(A B C) '(B A D))
(A B C D)

Another, less efficient, way is to change the algorithm by taking into account unordered lists.

Finally note that the third branch of the outer conditional is never statisfied: ((and (null lst1) (null lst2)) nil)

This is because, in this case, the first branch is true and the function returns nil.