## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.62

From Drewiki

## Problem

Give a θ(*n*) implementation of `union-set` for sets represented as ordered lists.

## Solution

The overall structure of a θ(*n*) implementation of `union-set` is similar to that given in the text for `intersection-set`. The chief difference is that `union-set` always `cons`es the lesser element from `set1` or `set2` onto the result of the recursion. The decision of which set to `cdr` is identical to that of `intersection-set` (i.e., it's the one whose element is `cons`ed onto the result).

(define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set2))) (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2)))) ((< x1 x2) (cons x1 (union-set (cdr set1) set2))) (else (cons x2 (union-set set1 (cdr set2)))))))))

Tests:

(define s1 '(1 3 6)) (define s2 '(2 3 4 7)) (union-set s1 s2)

*Output:*

`
`

(1 2 3 4 6 7)

(union-set s2 s1)

*Output:*

`
`

(1 2 3 4 6 7)

(union-set s1 '())

*Output:*

`
`

(1 3 6)

(union-set '() s1)

*Output:*

`
`

(1 3 6)