<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Apr 18, 2023 at 5:24 PM Daniel Baston <<a href="mailto:dbaston@gmail.com">dbaston@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div> but performs better than the old algorithm if the inputs are pre-sorted (as they are in the old algorithm). Maybe the same sorting should be added to the NG version.</div></div></blockquote><div><br></div><div>The first step in the union algorithm is to identify segments which are unique (duplicate segments are removed).  This is done by adding and removing segments to/from a set.  I wonder if it would be faster to simply sort all the segments, and scan the list retaining only unique segments? </div></div></div>