I need to join two lists, sort them and remove duplicates. Is there a better way to do this?

Question

I have two unsorted lists and I need to produce another list which is sorted and where all the elements are unique.

The elements can occur multiple times in both lists and they are originally unsorted.

My function looks like this:

(defun merge-lists (list-a list-b sort-fn)
    "Merges two lists of (x, y) coordinates sorting them and removing dupes"
    (let   ((prev nil))
        (remove-if
            (lambda (point)
                (let   ((ret-val (equal point prev)))
                    (setf prev point)
                    ret-val))
            (sort
                (merge 'list list-a list-b sort-fn) ;'
                 sort-fn))))

Is there a better way to achieve the same?

Sample call:

[CL]> (merge-lists '(9 8 4 8 9 7 2) '(1 7 3 9 2 6) #'>)
  ==> (9 8 7 6 4 3 2 1)

Answer 1

Our neighbourhood friendly Lisp guru pointed out the remove-duplicates function.

He also provided the following snippet:

(defun merge-lists (list-a list-b sort-fn test-fn)
    (sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn))

Answer 2

I think I would first sort the two lists separately and then merge them with a function that also skips over duplicates. This should be a bit faster as it requires one less traversal of both lists.

P.S.: I doubt it can be done much faster as you basically always need at least one sort and one merge. Perhaps you can combine both in one function, but I wouldn't be surprised if that doesn't make a (big) difference.