if you will take a closer look (actually you will find a comment
"perform the binary search"), you will see that 'AddSet' uses a binary
search, *but* it has to ensure that the list is indeed a set. To the
inexperienced user a simple solution to the problem is

It is not quite clear why faster ways to handle sets, such that the
addition of a new element takes only O(log(N)) operations, are not used
in the GAP implementation.

but this naive approach has a drawback, namely that sets in this
proposal could only contain unchangeable data structures like integers
or permutations but not changeable like lists or records without
introducing some amount of overhead for *all* list/record assignments.
To illustrate the point, consider the following examples:

There is another problem, which I outlined to Martin a while ago.
Once it has decided where in the set the new entry is to be added,
AddSet then has to do O(N) work to make room for it by moving half
the set. The constant is pretty low, but it's still O(N).

My solution to this is to use blists rather than sets whenever
possible, and I have functions FastOrbit and FastOrbits which do
this, and differ from Orbit only in that they require the domain to
be given in full. Ideally functions like the Random Schreier-Sims
should use these techniques also.

Steve